Local Search for Clustering in Almost-linear Time

Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou +1

We propose the first \emph{local search} algorithm for Euclidean clustering that attains an $O(1)$-approximation in almost-linear time. Specifically, for Euclidean $k$-Means, our a…