# On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2020.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (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)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Modification-Fair Cluster Editing](https://mlsanity.com/paper/2112.03183/) (2021)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [Fair Minimum Representation Clustering](https://mlsanity.com/paper/2302.03151/) (2023)
- [Fair Correlation Clustering in Forests](https://mlsanity.com/paper/2302.11295/) (2023)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Fair Clustering with Minimum Representation Constraints](https://mlsanity.com/paper/2409.02963/) (2024)
- [Fair Clustering with Clusterlets](https://mlsanity.com/paper/2505.06259/) (2025)
- [Fair Dataset Distillation via Cross-Group Barycenter Alignment](https://mlsanity.com/paper/2605.00185/) (2026)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS, 2017] in a seminal work and became widely popular in the clustering literature. In this paper, we propose a new construction of coresets for fair clustering based on random sampling. The new construction allows us to obtain the first coreset for fair clustering in general metric spaces. For Euclidean spaces, we obtain the first coreset whose size does not depend exponentially on the dimension. Our coreset results solve open questions proposed by Schmidt et al. [WAOA, 2019] and Huang et al. [NeurIPS, 2019]. The new coreset construction helps to design several new approximation and streaming algorithms. In particular, we obtain the first true constant-approximation algorithm for metric fair clustering, whose running time is fixed-parameter tractable (FPT). In the Euclidean case, we derive the first (1+ε)-approximation algorithm for fair clustering whose time complexity is near-linear and does not depend exponentially on the dimension of the space. Besides, our coreset construction scheme is fairly general and gives rise to coresets for a wide range of constrained clustering problems. This leads to improved constant-approximations for these problems in general metrics and near-linear time (1+ε)-approximations in the Euclidean metric.