← 研踪 PaperTrailarXiv:2609.07974 · v2
A Tight 3-Approximation for Fair $k$-Means
首次提交 2026-09-08 04:54
版本更新 2026-10-28 01:56
雷达观测 2026-10-29 00:34
摘要
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. Our algorithm first splits the input into many small fair clusters and then merges them into $k$ clusters with a weighted $k$-means algorithm. The merge is cheap only when the small clusters do not move points away from their optimal centers, so we add a displacement penalty to the split, which charges each point for how far the small clusters move it. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $3ρ+ε$ times the optimal integral fair cost. With a PTAS as the subroutine, the approximation ratio becomes $3+O(ε)$, improving the previous factor of $5+O(ε)$. This ratio is the best possible: unless P=NP, no polynomial-time algorithm achieves the ratio $3-δ$ for any fixed $δ>0$, even in one dimension. 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-28 01:56 · 最新观测版本
A Tight 3-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. Our algorithm first splits the input into many small fair clusters and then merges them into $k$ clusters with a weighted $k$-means algorithm. The merge is cheap only when the small clusters do not move points away from their optimal centers, so we add a displacement penalty to the split, which charges each point for how far the small clusters move it. Given a $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $3ρ+ε$ times the optimal integral fair cost. With a PTAS as the subroutine, the approximation ratio becomes $3+O(ε)$, improving the previous factor of $5+O(ε)$. This ratio is the best possible: unless P=NP, no polynomial-time algorithm achieves the ratio $3-δ$ for any fixed $δ>0$, even in one dimension. 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.
查看此版本解读 →查看此版本原文 ↗