# Individual Fairness for k-Clustering

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

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

- [A survey on datasets for fairness-aware machine learning](https://mlsanity.com/paper/2110.00530/) (2021)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metric](https://mlsanity.com/paper/2209.12396/) (2022)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Deep Fair Discriminative Clustering](https://mlsanity.com/paper/2105.14146/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (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)
- [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)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Learning to Generate Fair Clusters from Demonstrations](https://mlsanity.com/paper/2102.03977/) (2021)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (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)
- [Models and Mechanisms for Spatial Data Fairness](https://mlsanity.com/paper/2204.01880/) (2022)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)

## Abstract (arXiv)

We give a local search based algorithm for k-median and k-means (and more generally for any k-clustering with ℓp norm cost function) from the perspective of individual fairness. More precisely, for a point x in a point set P of size n, let r(x) be the minimum radius such that the ball of radius r(x) centered at x has at least n/k points from P. Intuitively, if a set of k random points are chosen from P as centers, every point x∈ P expects to have a center within radius r(x). An individually fair clustering provides such a guarantee for every point x∈ P. This notion of fairness was introduced in [Jung et al., 2019] where they showed how to get an approximately feasible k-clustering with respect to this fairness condition. In this work, we show how to get a bicriteria approximation for fair k-clustering: The k-median (k-means) cost of our solution is within a constant factor of the cost of an optimal fair k-clustering, and our solution approximately satisfies the fairness condition (also within a constant factor). Further, we complement our theoretical bounds with empirical evaluation.