mlsanityData to 7 Oct 2026

Fair k-Center Clustering for Data Summarization

arXiv 1901.08628 ↗First posted 24 Jan 2019stat.ML cs.DS cs.LGcited by 65

Not on the map. Why?

Abstract (arXiv)

In data summarization we want to choose k prototypes in order to summarize a data set. We study a setting where the data set comprises several demographic groups and we are restricted to choose ki prototypes belonging to group i. A common approach to the problem without the fairness constraint is to optimize a centroid-based clustering objective such as k-center. A natural extension then is to incorporate the fairness constraint into the clustering problem. Existing algorithms for doing so run in time super-quadratic in the size of the data set, which is in contrast to the standard k-center problem being approximable in linear time. In this paper, we resolve this gap by providing a simple approximation algorithm for the k-center problem under the fairness constraint with running time linear in the size of the data set and k. If the number of demographic groups is small, the approximation guarantee of our algorithm only incurs a constant-factor overhead.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 20; 2023: 9; 2024: 9; 2025: 5; 2026: 5.

65 papers.

Sort:

  1. 2022The Hidden Uniform Cluster Prior in Self-Supervised Learningcited by 57
  2. 2021Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Informationcited by 33
  3. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  4. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  5. 2021A Sociotechnical View of Algorithmic Fairnesscited by 24
  6. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  7. 2022Deep Fair Clustering via Maximizing and Minimizing Mutual Information: Theory, Algorithm and Metriccited by 17
  8. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  9. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  10. 2022Robust Fair Clustering: A Novel Fairness Attack and Defense Frameworkcited by 13
  11. 2021Deep Fair Discriminative Clusteringcited by 10
  12. 2021A Stochastic Alternating Balance k-Means Algorithm for Fair Clusteringcited by 10
38 more
  1. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  2. 2022Fairness-aware Model-agnostic Positive and Unlabeled Learningcited by 10
  3. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  4. 2021Multiple-criteria Based Active Learning with Fixed-size Determinantal Point Processescited by 9
  5. 2023Doubly Constrained Fair Clusteringcited by 9
  6. 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
  7. 2022Individual Preference Stability for Clusteringcited by 8
  8. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  9. 2023R3-NL2GQL: A Model Coordination and Knowledge Graph Alignment Approach for NL2GQLcited by 7
  10. 2021Pairwise Fairness for Ordinal Regressioncited by 6
  11. 2022Improved Approximation for Fair Correlation Clusteringcited by 6
  12. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  13. 2022Emergent specialization from participation dynamics and multi-learner retrainingcited by 5
  14. 2021Learning to Generate Fair Clusters from Demonstrationscited by 4
  15. 2021How to Design Robust Algorithms using Noisy Comparison Oraclecited by 4
  16. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  17. 2022Fair Representation Clustering with Several Protected Classescited by 4
  18. 2022Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Costcited by 4
  19. 2022Streaming Algorithms for Diversity Maximization with Fairness Constraintscited by 3
  20. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  21. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  22. 2021NNK-Means: Data summarization using dictionary learning with non-negative kernel regressioncited by 2
  23. 2022Fair Labeled Clusteringcited by 2
  24. 2022Balancing Utility and Fairness in Submodular Maximization (Technical Report)cited by 2
  25. 2023Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithmscited by 2
  26. 2024Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledgecited by 2
  27. 2024Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insightscited by 2
  28. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  29. 2022No More Than 6ft Apart: Robust K-Means via Radius Upper Boundscited by 1
  30. 2022Exploring Rawlsian Fairness for K-Means Clusteringcited by 1
  31. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  32. 2022Towards Auditing Unsupervised Learning Algorithms and Human Processes For Fairnesscited by 1
  33. 2022A Global Optimization Algorithm for K-Center Clustering of One Billion Samplescited by 1
  34. 2023Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outlierscited by 1
  35. 2023Fair Clustering via Hierarchical Fair-Dirichlet Processcited by 1
  36. 2023Fair Clustering: A Causal Perspectivecited by 1
  37. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  38. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1

50 most cited of 65 All 65 (JSON)