# Fair Clustering Under a Bounded Cost

arXiv: https://arxiv.org/abs/2106.07239 · HTML: https://mlsanity.com/paper/2106.07239/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [Improving fairness in machine learning systems: What do industry practitioners need?](https://mlsanity.com/paper/1812.05239/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [Fair Hierarchical Clustering](https://mlsanity.com/paper/2006.10221/) (2020)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms During High-Demand Hours](https://mlsanity.com/paper/1912.08388/) (2019)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering](https://mlsanity.com/paper/2105.14172/) (2021)
- [Fair Clustering with Multiple Colors](https://mlsanity.com/paper/2002.07892/) (2020)
- [Balancing Lexicographic Fairness and a Utilitarian Objective with Application to Kidney Exchange](https://mlsanity.com/paper/1702.08286/) (2017)

## Built on by (most cited first, 21 of 21)

- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Learning Informative Representation for Fairness-aware Multivariate Time-series Forecasting: A Group-based Perspective](https://mlsanity.com/paper/2301.11535/) (2023)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Fair Representation Clustering with Several Protected Classes](https://mlsanity.com/paper/2202.01391/) (2022)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [Holistic Survey of Privacy and Fairness in Machine Learning](https://mlsanity.com/paper/2307.15838/) (2023)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [Fair Labeled Clustering](https://mlsanity.com/paper/2205.14358/) (2022)
- [Dual Node and Edge Fairness-Aware Graph Partition](https://mlsanity.com/paper/2306.10123/) (2023)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [Fair Clustering via Alignment](https://mlsanity.com/paper/2505.09131/) (2025)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Fair Bayesian Model-Based Clustering](https://mlsanity.com/paper/2506.12839/) (2025)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)
- [Fair Model-based Clustering](https://mlsanity.com/paper/2602.21509/) (2026)
- [Fast and effective algorithms for fair clustering at scale](https://mlsanity.com/paper/2605.13759/) (2026)
- [COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering](https://mlsanity.com/paper/2607.18119/) (2026)

## Abstract (arXiv)

Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the ''price of fairness,'' can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.