mlsanityData to 7 Oct 2026

Fair Algorithms for Clustering

arXiv 1901.02393 ↗First posted 8 Jan 2019cs.DS cs.LGcited by 98

Not on the map. Why?

Abstract (arXiv)

We study the problem of finding low-cost Fair Clusterings in data where each data point may belong to many protected groups. Our work significantly generalizes the seminal work of Chierichetti et.al. (NIPS 2017) as follows. - We allow the user to specify the parameters that define fair representation. More precisely, these parameters define the maximum over- and minimum under-representation of any group in any cluster. - Our clustering algorithm works on any ℓp-norm objective (e.g. k-means, k-median, and k-center). Indeed, our algorithm transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. - Our algorithm also allows individuals to lie in multiple protected groups. In other words, we do not need the protected groups to partition the data and we can maintain fairness across different groups simultaneously. Our experiments show that on established data sets, our algorithm performs much better in practice than what our theoretical results suggest.

Key facts. Cited by 98 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 30; 2022: 14; 2023: 16; 2024: 19; 2025: 12; 2026: 7.

98 papers.

Sort:

  1. 2021A survey on datasets for fairness-aware machine learningcited by 157
  2. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  3. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  4. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  5. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  6. 2021Fair Clustering Under a Bounded Costcited by 21
  7. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  8. 2021Fast and Efficient MMD-based Fair PCA via Optimization over Stiefel Manifoldcited by 18
  9. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  10. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  11. 2022Scalable Spectral Clustering with Group Fairness Constraintscited by 16
  12. 2021Fair Enough: Searching for Sufficient Measures of Fairnesscited by 14
38 more
  1. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  2. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  3. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  4. 2021Deep Fair Discriminative Clusteringcited by 10
  5. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  6. 2021Fair Clustering Using Antidote Datacited by 10
  7. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  8. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  9. 2021Fair-Capacitated Clusteringcited by 9
  10. 2023Doubly Constrained Fair Clusteringcited by 9
  11. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  12. 2023Proportionally Representative Clusteringcited by 8
  13. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  14. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  15. 2021Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problemcited by 5
  16. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  17. 2021Fairness Degrading Adversarial Attacks Against Clustering Algorithmscited by 5
  18. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  19. 2024Local Causal Discovery with Background Knowledgecited by 5
  20. 2021Learning to Generate Fair Clusters from Demonstrationscited by 4
  21. 2021Revisiting Priority k-Center: Fairness and Outlierscited by 4
  22. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  23. 2021Tight FPT Approximation for Constrained k-Center and k-Suppliercited by 4
  24. 2022Fair Representation Clustering with Several Protected Classescited by 4
  25. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  26. 2021Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?cited by 3
  27. 2023A review of clustering models in educational data science towards fairness-aware learningcited by 3
  28. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  29. 2023A Unified Framework for Fair Spectral Clustering With Effective Graph Learningcited by 3
  30. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  31. 2021Fair Disaster Containment via Graph-Cut Problemscited by 2
  32. 2022Fair Labeled Clusteringcited by 2
  33. 2023Achieving Long-term Fairness in Submodular Maximization through Randomizationcited by 2
  34. 2023Fair Polylog-Approximate Low-Cost Hierarchical Clusteringcited by 2
  35. 2024Perceptual Fairness in Image Restorationcited by 2
  36. 2024Outlier Detection Bias Busted: Understanding Sources of Algorithmic Bias through Data-centric Factorscited by 2
  37. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  38. 2021FiSH: Fair Spatial Hotspotscited by 1

50 most cited of 98 All 98 (JSON)