A Refined Approximation for Euclidean k-Means

Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani +2

In the Euclidean $k$-Means problem we are given a collection of $n$ points $D$ in an Euclidean space and a positive integer $k$. Our goal is to identify a collection of $k$ points…