# Spectral Dual Fitting for k-Means

arXiv: https://arxiv.org/abs/2607.14654 · HTML: https://mlsanity.com/paper/2607.14654/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

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.