[Submitted on 7 Sep 2026 (v1), last revised 3 Nov 2026 (this version, v3)]
Abstract: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 $2rho+1+epsilon$ times the fractional optimum, improving the previous ratio $1+4rho+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.
Submission history
From: Kangke Cheng [view email]
[v1] Mon, 7 Sep 2026 20:54:36 UTC (36 KB)
[v2] Tue, 27 Oct 2026 17:56:47 UTC (47 KB)
[v3] Tue, 3 Nov 2026 13:08:05 UTC (74 KB)