# On the cost of essentially fair clusterings

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2018.

## Built on by (most cited first, 30 of 44)

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Fair Clustering Using Antidote Data](https://mlsanity.com/paper/2106.00600/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [Doubly Constrained Fair Clustering](https://mlsanity.com/paper/2305.19475/) (2023)
- [Individual Preference Stability for Clustering](https://mlsanity.com/paper/2207.03600/) (2022)
- [ExMap: Leveraging Explainability Heatmaps for Unsupervised Group Robustness to Spurious Correlations](https://mlsanity.com/paper/2403.13870/) (2024)
- [Improved Approximation for Fair Correlation Clustering](https://mlsanity.com/paper/2206.05050/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Fairness Degrading Adversarial Attacks Against Clustering Algorithms](https://mlsanity.com/paper/2110.12020/) (2021)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)
- [Feature-based Individual Fairness in k-Clustering](https://mlsanity.com/paper/2109.04554/) (2021)
- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (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)
- [Spectral Normalized-Cut Graph Partitioning with Fairness Constraints](https://mlsanity.com/paper/2307.12065/) (2023)
- [Fair Disaster Containment via Graph-Cut Problems](https://mlsanity.com/paper/2106.05424/) (2021)
- [Fair Labeled Clustering](https://mlsanity.com/paper/2205.14358/) (2022)
- [Fair Polylog-Approximate Low-Cost Hierarchical Clustering](https://mlsanity.com/paper/2311.12501/) (2023)
- [Perceptual Fairness in Image Restoration](https://mlsanity.com/paper/2405.13805/) (2024)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Fair Clustering: A Causal Perspective](https://mlsanity.com/paper/2312.09061/) (2023)
- [Scalable Algorithms for Individual Preference Stable Clustering](https://mlsanity.com/paper/2403.10365/) (2024)
- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)

## Abstract (arXiv)

Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters -- especially if the data is already biased. At NIPS 2017, Chierichetti et al. proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair k-center problem and a O(t)-approximation for the fair k-median problem, where t is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair k-center. We extend and improve the known results. Firstly, we give a 5-approximation for the fair k-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives k-center, k-supplier, k-median, k-means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed.