# Approximation Algorithms for Fair Range Clustering

arXiv: https://arxiv.org/abs/2306.06778 · HTML: https://mlsanity.com/paper/2306.06778/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 11 Jun 2023.

## Builds on (most cited first, 30 of 31)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Diversity-aware k-median : Clustering with fair center representation](https://mlsanity.com/paper/2106.11696/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [Near Neighbor: Who is the Fairest of Them All?](https://mlsanity.com/paper/1906.02640/) (2019)
- [Fair Near Neighbor Search: Independent Range Sampling in High Dimensions](https://mlsanity.com/paper/1906.01859/) (2019)
- [Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications](https://mlsanity.com/paper/1310.7834/) (2013)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Fair Range k-center](https://mlsanity.com/paper/2207.11337/) (2022)

## Built on by (most cited first, 10 of 10)

- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights](https://mlsanity.com/paper/2410.12913/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [Unbiased Binning for Fairness-aware Attribute Representation](https://mlsanity.com/paper/2509.21785/) (2025)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [On the Hardness of Approximation of the Fair k-Center Problem](https://mlsanity.com/paper/2602.16688/) (2026)

## Abstract (arXiv)

This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick k centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of n points in a metric space (P,d) where each point belongs to one of the ℓ different demographics (i.e., P = P1 uplus P2 uplus cdots uplus Pℓ) and a set of ℓ intervals [α1, β1], cdots, [αℓ, βℓ] on desired number of centers from each group, the goal is to pick a set of k centers C with minimum ℓp-clustering cost (i.e., (sumv∈ P d(v,C)p)1/p) such that for each group i∈ ℓ, |Ccap Pi| ∈ [αi, βi]. In particular, the fair range ℓp-clustering captures fair range k-center, k-median and k-means as its special cases. In this work, we provide efficient constant factor approximation algorithms for fair range ℓp-clustering for all values of p∈ [1,∞).