# Improved Approximation Algorithms for Individually Fair Clustering

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 26 Jun 2021.

## Builds on (most cited first, 27 of 27)

- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [The Frontiers of Fairness in Machine Learning](https://mlsanity.com/paper/1810.08810/) (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)
- [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)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [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)
- [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)
- [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)
- [A Notion of Individual Fairness for Clustering](https://mlsanity.com/paper/2006.04960/) (2020)
- [Auditing for Discrimination in Algorithms Delivering Job Ads](https://mlsanity.com/paper/2104.04502/) (2021)
- [Distributional Individual Fairness in Clustering](https://mlsanity.com/paper/2006.12589/) (2020)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Near Neighbor: Who is the Fairest of Them All?](https://mlsanity.com/paper/1906.02640/) (2019)
- [New Approximability Results for the Robust k-Median Problem](https://mlsanity.com/paper/1309.4602/) (2013)
- [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)
- [Structural Iterative Rounding for Generalized k-Median Problems](https://mlsanity.com/paper/2009.00808/) (2020)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)

## Built on by (most cited first, 30 of 33)

- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [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)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Fair Wasserstein Coresets](https://mlsanity.com/paper/2311.05436/) (2023)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [FAL-CUR: Fair Active Learning using Uncertainty and Representativeness on Fair Clustering](https://mlsanity.com/paper/2209.12756/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [Constant Approximation for Individual Preference Stable Clustering](https://mlsanity.com/paper/2309.16840/) (2023)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolina](https://mlsanity.com/paper/2205.14867/) (2022)
- [Sanitized Clustering against Confounding Bias](https://mlsanity.com/paper/2311.01252/) (2023)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [Linear Programming based Approximation to Individually Fair k-Clustering with Outliers](https://mlsanity.com/paper/2412.10923/) (2024)
- [Adversarial Fair Multi-View Clustering](https://mlsanity.com/paper/2508.04071/) (2025)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Bicriteria Approximation Algorithms for Priority Matroid Median](https://mlsanity.com/paper/2210.01888/) (2022)
- [Can Evolutionary Clustering Have Theoretical Guarantees?](https://mlsanity.com/paper/2212.01771/) (2022)
- [Cluster-level Group Representativity Fairness in k-means Clustering](https://mlsanity.com/paper/2212.14467/) (2022)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Efficient k-means with Individual Fairness via Exponential Tilting](https://mlsanity.com/paper/2406.16557/) (2024)

## Abstract (arXiv)

We consider the k-clustering problem with ℓp-norm cost, which includes k-median, k-means and k-center, under an individual notion of fairness proposed by Jung et al. [2020]: given a set of points P of size n, a set of k centers induces a fair clustering if every point in P has a center among its n/k closest neighbors. Mahabadi and Vakilian [2020] presented a (pO(p),7)-bicriteria approximation for fair clustering with ℓp-norm cost: every point finds a center within distance at most 7 times its distance to its (n/k)-th closest neighbor and the ℓp-norm cost of the solution is at most pO(p) times the cost of an optimal fair solution. In this work, for any varepsilon>0, we present an improved (16p +varepsilon,3)-bicriteria for this problem. Moreover, for p=1 (k-median) and p=∞ (k-center), we present improved cost-approximation factors 7.081+varepsilon and 3+varepsilon respectively. To achieve our guarantees, we extend the framework of [Charikar et al., 2002, Swamy, 2016] and devise a 16p-approximation algorithm for the facility location with ℓp-norm cost under matroid constraint which might be of an independent interest. Besides, our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement proposed by Kleindessner et al. [2019], which is essentially the median matroid problem [Krishnaswamy et al., 2011].