Spectral Dual Fitting for $k$-Means
TL;DR
A new dual fitting algorithm is given which tightly accounts for dual payments while still facilitating an effective dual feasibility analysis, and a new framework that uses spectral analysis for determining the approximation factor of the algorithm is introduced.
Abstract
We give a new dual fitting algorithm which gives improved approximation ratios of $3+\ln 2 + \epsilon\ (\approx 3.694)$ and $4.9+\epsilon$ for $k$-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of $4+\epsilon$ [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and $5+\epsilon$ [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean $k$-Means breaks the hardness barrier of $1+8/e\approx 3.94$ for Metric $k$-Means. Prior to our work, no such separation between general and Euclidean metrics was known for $k$-Median, $k$-Means, or Facility Location in terms of their approximability. Unlike prior dual fitting approaches for $k$-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.