Spectral Dual Fitting for k-Means

We give a new dual fitting algorithm which gives improved approximation ratios of 3+ln 2 + ε (≈ 3.694) and 4.9+ε for k-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of 4+ε [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and 5+ε [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≈ 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.