mlsanityData to 7 Oct 2026

A Scalable Algorithm for Individually Fair K-means Clustering

arXiv 2402.06730 ↗First posted 9 Feb 2024cs.DS cs.CY cs.LGcited by 8

Not on the map. Why?

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.

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

Builds on

31 of 73 references.

References · 31

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2019Fair Algorithms for Clusteringcited by 98
  3. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  4. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  5. 2020Individual Fairness for k-Clusteringcited by 56
  6. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  7. 2019Clustering without Over-Representationcited by 50
  8. 2020Fair clustering via equitable group representationscited by 43
  9. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  10. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  11. 2020Fair Correlation Clusteringcited by 27
  12. 2020Fair Hierarchical Clusteringcited by 25
19 more
  1. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  2. 2022The Power of Uniform Sampling for Coresetscited by 18
  3. 2020k-means++: few more steps yield constant approximationcited by 16
  4. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  5. 2020On Approximability of Clustering Problems Without Candidate Centerscited by 13
  6. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  7. 2018Approximation Algorithms for Minimum Norm and Ordered Optimization Problemscited by 11
  8. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  9. 2017Constant-Factor Approximation for Ordered k-Mediancited by 8
  10. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  11. 2020Sliding Window Algorithms for k-Clustering Problemscited by 7
  12. 2017Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Mediancited by 6
  13. 2020Decorrelated Clustering with Data Selection Biascited by 6
  14. 2021Robust Trimmed k-meanscited by 5
  15. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  16. 2021Revisiting Priority k-Center: Fairness and Outlierscited by 4
  17. 2023Multi-Swap k-Means++cited by 4
  18. 2021Modification-Fair Cluster Editingcited by 3
  19. 2022No More Than 6ft Apart: Robust K-Means via Radius Upper Boundscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 2.

8 papers.

  1. 2025KNN and K-means in Gini Prametric Spacescited by 2
  2. 2024The Fairness-Quality Trade-off in Clusteringcited by 1
  3. 2024Linear Programming based Approximation to Individually Fair k-Clustering with Outlierscited by 1
  4. 2025Adversarial Fair Multi-View Clusteringcited by 1
  5. 2024Efficient k-means with Individual Fairness via Exponential Tiltingcited by 0
  6. 2025A Deep Latent Factor Graph Clustering with Fairness-Utility Trade-off Perspectivecited by 0
  7. 2026Individual Fairness in Hierarchical Clusteringcited by 0
  8. 2026Multi-View Fair Clustering Guided by Cross-View Sensitive Information Discrepancycited by 0