Local Search for Clustering in Almost-linear Time

We propose the first local search algorithm for Euclidean clustering that attains an \(O(1)\)-approximation in almost-linear time. Specifically, for Euclidean \(k\)-Means, our algorithm achieves an \(O(c)\)-approximation in \(\tilde O(n^{1+1/c})\) time, for any constant \(c \ge 1\), maintaining the same running time as the previous (non-local-search-based) approach [la Tour and Saulpic, arXiv’2407.11217] while improving the approximation factor from \(O(c^6)\) to \(O(c)\). The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in \(\ell_p\) metrics, doubling metrics, Jaccard metrics, etc.