mlsanityData to 14 Oct 2026

Scalable Fair Clustering

arXiv 1902.03519 ↗First posted 10 Feb 2019cs.DS cs.LGcited by 78

Not on the map. Why?

Abstract (arXiv)

We study the fair variant of the classic k-median problem introduced by Chierichetti et al. [2017]. In the standard k-median problem, given an input pointset P, the goal is to find k centers C and assign each input point to one of the centers in C such that the average distance of points to their cluster center is minimized. In the fair variant of k-median, the points are colored, and the goal is to minimize the same average distance objective while ensuring that all clusters have an "approximately equal" number of points of each color. Chierichetti et al. proposed a two-phase algorithm for fair k-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time. Our algorithm additionally allows for finer control over the balance of resulting clusters than the original work. We complement our theoretical bounds with empirical evaluation.

Key facts. Cited by 78 papers in the map (data through 14 Oct 2026). First posted on arXiv 10 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 25; 2022: 10; 2023: 12; 2024: 16; 2025: 10; 2026: 5.

78 papers.

Sort:

By area:

  1. 2021A survey on datasets for fairness-aware machine learningcited by 157
  2. 2021Trustworthy AI: A Computational Perspectivecited by 93
  3. 2022Fair and Optimal Classification via Post-Processingcited by 51
  4. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  5. 2023Inductive Graph Unlearningcited by 31
  6. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  7. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  8. 2021Fair Clustering Under a Bounded Costcited by 21
  9. 2021The Authors Matter: Understanding and Mitigating Implicit Bias in Deep Text Classificationcited by 18
  10. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  11. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  12. 2021Modeling Techniques for Machine Learning Fairness: A Surveycited by 17
38 more
  1. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  2. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  3. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  4. 2022Robust Fair Clustering: A Novel Fairness Attack and Defense Frameworkcited by 13
  5. 2021Deep Fair Discriminative Clusteringcited by 10
  6. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  7. 2021Fair Clustering Using Antidote Datacited by 10
  8. 2021Fairness-Aware Unsupervised Feature Selectioncited by 10
  9. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  10. 2021Fair-Capacitated Clusteringcited by 9
  11. 2022Individual Preference Stability for Clusteringcited by 8
  12. 2023Proportionally Representative Clusteringcited by 8
  13. 2023Fair Wasserstein Coresetscited by 8
  14. 2021Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problemcited by 5
  15. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  16. 2021Fairness Degrading Adversarial Attacks Against Clustering Algorithmscited by 5
  17. 2024Local Causal Discovery with Background Knowledgecited by 5
  18. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  19. 2022Fair Representation Clustering with Several Protected Classescited by 4
  20. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  21. 2021Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?cited by 3
  22. 2021Fairness-aware Outlier Ensemblecited by 3
  23. 2023A review of clustering models in educational data science towards fairness-aware learningcited by 3
  24. 2023Improving Fairness with Ensemble Combination: Margin-Dependent Boundscited by 3
  25. 2023Fairness in Streaming Submodular Maximization over a Matroid Constraintcited by 3
  26. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  27. 2023A Unified Framework for Fair Spectral Clustering With Effective Graph Learningcited by 3
  28. 2021Fair Disaster Containment via Graph-Cut Problemscited by 2
  29. 2022Fair Labeled Clusteringcited by 2
  30. 2024Measuring Model-Induced Discrimination via Efficient Fairness Approximationcited by 2
  31. 2024Perceptual Fairness in Image Restorationcited by 2
  32. 2024Outlier Detection Bias Busted: Understanding Sources of Algorithmic Bias through Data-centric Factorscited by 2
  33. 2024Towards a Fairer Non-negative Matrix Factorizationcited by 2
  34. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  35. 2022Modeling Human Behavior Part II -- Cognitive approaches and Uncertaintycited by 1
  36. 2022Fair Inference for Discrete Latent Variable Modelscited by 1
  37. 2022Towards Auditing Unsupervised Learning Algorithms and Human Processes For Fairnesscited by 1
  38. 2023Bias Mitigation Methods for Binary Classification Decision-Making Systems: Survey and Recommendationscited by 1

50 most cited of 78 All 78 (JSON)