mlsanityData to 7 Oct 2026

Clustering without Over-Representation

arXiv 1905.12753 ↗First posted 29 May 2019cs.DS cs.LGcited by 50

Not on the map. Why?

Abstract (arXiv)

In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the additional constraint that no color is over-represented in any cluster. This problem is motivated by practical clustering settings, e.g., in clustering news articles where the color of an article is its source, it is preferable that no single news source dominates any cluster. For the most general version of this problem, we obtain an algorithm that has provable guarantees of performance; our algorithm is based on finding a fractional solution using a linear program and rounding the solution subsequently. For the special case of the problem where no color has an absolute majority in any cluster, we obtain a simpler combinatorial algorithm also with provable guarantees. Experiments on real-world data shows that our algorithms are effective in finding good clustering without over-representation.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 10; 2023: 7; 2024: 9; 2025: 4; 2026: 3.

50 papers.

Sort:

  1. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  2. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  3. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  4. 2021Fair Clustering Under a Bounded Costcited by 21
  5. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  6. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  7. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  8. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  9. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  10. 2021Deep Fair Discriminative Clusteringcited by 10
  11. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
  12. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
38 more
  1. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  2. 2023Doubly Constrained Fair Clusteringcited by 9
  3. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  4. 2022Individual Preference Stability for Clusteringcited by 8
  5. 2023Proportionally Representative Clusteringcited by 8
  6. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  7. 2024ExMap: Leveraging Explainability Heatmaps for Unsupervised Group Robustness to Spurious Correlationscited by 8
  8. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  9. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  10. 2021Learning to Generate Fair Clusters from Demonstrationscited by 4
  11. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  12. 2022Fair Representation Clustering with Several Protected Classescited by 4
  13. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  14. 2023A review of clustering models in educational data science towards fairness-aware learningcited by 3
  15. 2021Fair Disaster Containment via Graph-Cut Problemscited by 2
  16. 2022Fair Labeled Clusteringcited by 2
  17. 2023Fair Polylog-Approximate Low-Cost Hierarchical Clusteringcited by 2
  18. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  19. 2023Fair Clustering: A Causal Perspectivecited by 1
  20. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  21. 2024Robust Fair Clustering with Group Membership Uncertainty Setscited by 1
  22. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  23. 2024The Fairness-Quality Trade-off in Clusteringcited by 1
  24. 2026Evaluating Interactive 2D Visualization as a Sample Selection Strategy for Biomedical Time-Series Data Annotationcited by 1
  25. 2021Coping with Mistreatment in Fair Algorithmscited by 0
  26. 2021CONFAIR: Configurable and Interpretable Algorithmic Fairnesscited by 0
  27. 2022On consistency of constrained spectral clustering under representation-aware stochastic block modelcited by 0
  28. 2022Cluster-level Group Representativity Fairness in k-means Clusteringcited by 0
  29. 2023Approximating Fair k-Min-Sum-Radii in Euclidean Spacecited by 0
  30. 2024From Discrete to Continuous: Deep Fair Clustering With Transferable Representationscited by 0
  31. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0
  32. 2024Fair Clustering with Minimum Representation Constraintscited by 0
  33. 2025FACROC: a fairness measure for FAir Clustering through ROC curvescited by 0
  34. 2025Accelerating Spectral Clustering under Fairness Constraintscited by 0
  35. 2025Welfare-Centric Clusteringcited by 0
  36. 2025Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equitycited by 0
  37. 2026SOMtime the World Ain't Fair: Violating Fairness Using Self-Organizing Mapscited by 0
  38. 2026Fast and effective algorithms for fair clustering at scalecited by 0