A Sub-4 Approximation for Fair $k$-Means
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 ...
| Authors | Kangke Cheng, Guanlin Mo, Shihong Song et al. |
|---|---|
| Primary category | cs.CG |
| Published | 7 September 2026 |
| Last updated at source | 7 September 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.