mlsanityData to 7 Oct 2026

Proportionally Fair Clustering

arXiv 1905.03674 ↗First posted 9 May 2019cs.LG cs.DS cs.GTcited by 69

Not on the map. Why?

Abstract (arXiv)

We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering n points with k centers, we define fairness as proportionality to mean that any n/k points are entitled to form their own cluster if there is another center that is closer in distance for all n/k points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the k-means objective.

Key facts. Cited by 69 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 11; 2023: 10; 2024: 12; 2025: 8; 2026: 8.

69 papers.

Sort:

  1. 2021Trustworthy AI: A Computational Perspectivecited by 93
  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. 2021Algorithm Fairness in AI for Medicine and Healthcarecited by 21
  7. 2021The Authors Matter: Understanding and Mitigating Implicit Bias in Deep Text Classificationcited by 18
  8. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  9. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  10. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  11. 2023Proportional Fairness in Clustering: A Social Choice Perspectivecited by 12
  12. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
38 more
  1. 2021Deep Fair Discriminative Clusteringcited by 10
  2. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  3. 2021Fair Clustering Using Antidote Datacited by 10
  4. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  5. 2022Fairness-aware Model-agnostic Positive and Unlabeled Learningcited by 10
  6. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  7. 2023Doubly Constrained Fair Clusteringcited by 9
  8. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  9. 2022Individual Preference Stability for Clusteringcited by 8
  10. 2023Proportionally Representative Clusteringcited by 8
  11. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  12. 2023Fairness-aware Multi-view Clusteringcited by 6
  13. 2024Proportional Fairness in Non-Centroid Clusteringcited by 6
  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. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  18. 2021Revisiting Priority k-Center: Fairness and Outlierscited 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. 2021Fairness-aware Outlier Ensemblecited by 3
  22. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  23. 2023Proportional Representation in Metric Spaces and Low-Distortion Committee Selectioncited by 3
  24. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  25. 2024Towards a Fairer Non-negative Matrix Factorizationcited by 2
  26. 2025Metritocracy: Representative Metrics for Lite Benchmarkscited by 2
  27. 2025Question the Questions: Auditing Representation in Online Deliberative Processescited by 2
  28. 2021Fairness Through Counterfactual Utilitiescited by 1
  29. 2022Exploring Rawlsian Fairness for K-Means Clusteringcited by 1
  30. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  31. 2023Fair Clustering via Hierarchical Fair-Dirichlet Processcited by 1
  32. 2023Fair Clustering: A Causal Perspectivecited by 1
  33. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  34. 2024The Fairness-Quality Trade-off in Clusteringcited by 1
  35. 2024Harm Ratio: A Novel and Versatile Fairness Criterioncited by 1
  36. 2024Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problemscited by 1
  37. 2024Linear Programming based Approximation to Individually Fair k-Clustering with Outlierscited by 1
  38. 2025Proportional Selection in Networkscited by 1

50 most cited of 69 All 69 (JSON)