Spectral Dual Fitting for $k$-Means

Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5

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 genera…