← 研踪 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 及以上也会标为版本更新。
v3 · 2026-11-03 21:08 · 最新观测版本
A $(3+ε)$-Approximation for Fair $k$-Means and a Matching Lower Bound
Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair $k$-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into $k$ fair clusters. Combined with any $ρ$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2ρ+1+ε$ times the fractional optimum, improving the previous ratio $1+4ρ+ε$. In fixed dimension, this improves the best known ratio from $5+O(ε)$ to $3+O(ε)$. The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a $(3-δ)$-approximation is NP-hard for every fixed $δ>0$, even on the line with fractional assignments, so $3$ is the exact approximation threshold for fractional fair $k$-means in fixed dimension. The same guarantees hold for $k$-sparse Wasserstein barycenters, a special case of fractional fair $k$-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.
查看此版本解读 →查看此版本原文 ↗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.
查看此版本解读 →查看此版本原文 ↗