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

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 $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.