Local Search Yields a PTAS for k-Means in Doubling Metrics

Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour

The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select…