arXiv:2609.07974v3 cs.CG

A $(3+\epsilon)$-Approximation for Fair $k$-Means and a Matching Lower Bound

Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding

제출 2026-11-04

원문 초록

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 $\rho$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2\rho+1+\epsilon$ times the fractional optimum, improving the previous ratio $1+4\rho+\epsilon$. In fixed dimension, this improves the best known ratio from $5+O(\epsilon)$ to $3+O(\epsilon)$. 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-\delta)$-approximation is NP-hard for every fixed $\delta>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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.07974v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.