# A Sub-4 Approximation for Fair k-Means

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 7 Sep 2026.

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

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [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)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [Stochastic Wasserstein Barycenters](https://mlsanity.com/paper/1802.05757/) (2018)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data](https://mlsanity.com/paper/1507.07218/) (2015)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Bayesian Learning with Wasserstein Barycenters](https://mlsanity.com/paper/1805.10833/) (2018)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [Faster Algorithms for the Constrained k-means Problem](https://mlsanity.com/paper/1504.02564/) (2015)
- [On the Computational Complexity of Finding a Sparse Wasserstein Barycenter](https://mlsanity.com/paper/1910.07568/) (2019)
- [A Unified Framework for Clustering Constrained Data without Locality Property](https://mlsanity.com/paper/1810.01049/) (2018)
- [A Refined Approximation for Euclidean k-Means](https://mlsanity.com/paper/2107.07358/) (2021)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [Fair Clustering in the Sliding Window Model](https://mlsanity.com/paper/2503.05173/) (2025)
- [Robust Fair Clustering with Group Membership Uncertainty Sets](https://mlsanity.com/paper/2406.00599/) (2024)
- [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)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Spectral Dual Fitting for k-Means](https://mlsanity.com/paper/2607.14654/) (2026)

## Abstract (arXiv)

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair k-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a ρ-approximate algorithm for weighted k-means and any ε>0, our algorithm returns a fractional solution whose cost is at most 1+(3-1/Gamma)ρ+O(ε) times the optimal integral fair cost, where Gamma≈6.357 is an upper bound on the integrality gap of the standard Euclidean k-means LP. With a PTAS as the subroutine, the approximation ratio becomes 3.8427+O(ε), improving the previous factor of 5+O(ε) to below 4. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the k-sparse Wasserstein barycenter problem.