# A Scalable Algorithm for Individually Fair K-means Clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 73 references that are in the map.
- First posted on arXiv 9 Feb 2024.

## 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)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [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)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [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)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Constant-Factor Approximation for Ordered k-Median](https://mlsanity.com/paper/1711.01972/) (2017)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Sliding Window Algorithms for k-Clustering Problems](https://mlsanity.com/paper/2006.05850/) (2020)
- [Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median](https://mlsanity.com/paper/1711.08715/) (2017)
- [Decorrelated Clustering with Data Selection Bias](https://mlsanity.com/paper/2006.15874/) (2020)
- [Robust Trimmed k-means](https://mlsanity.com/paper/2108.07186/) (2021)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)

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

- [KNN and K-means in Gini Prametric Spaces](https://mlsanity.com/paper/2501.18028/) (2025)
- [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)
- [Efficient k-means with Individual Fairness via Exponential Tilting](https://mlsanity.com/paper/2406.16557/) (2024)
- [A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspective](https://mlsanity.com/paper/2510.23507/) (2025)
- [Individual Fairness in Hierarchical Clustering](https://mlsanity.com/paper/2608.25586/) (2026)
- [Multi-View Fair Clustering Guided by Cross-View Sensitive Information Discrepancy](https://mlsanity.com/paper/2609.25811/) (2026)

## Abstract (arXiv)

We present a scalable algorithm for the individually fair (p, k)-clustering problem introduced by Jung et al. and Mahabadi et al. Given n points P in a metric space, let δ(x) for x∈ P be the radius of the smallest ball around x containing at least n / k points. A clustering is then called individually fair if it has centers within distance δ(x) of x for each x∈ P. While good approximation algorithms are known for this problem no efficient practical algorithms with good theoretical guarantees have been presented. We design the first fast local-search algorithm that runs in ~O(nk2) time and obtains a bicriteria (O(1), 6) approximation. Then we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.