Multi-Swap $k$-Means++
Lorenzo Beretta Vincent Cohen-Addad Silvio Lattanzi Nikos Parotsidis
The $k$-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often
the practitioners' choice algorithm for optimizing the popular $k$-means
clustering objective and is known to give an $O(\log k)$-approximation in
expectation. To obtain higher quality solutions, Lattanzi and Sohler (ICML
2019) proposed augmenting $k$-means++ with $O(k \log \log k)$ local search
steps obtained through the $k$-means++ sampling distribution to yield a
$c$-approximation to the $k$-means clustering problem, where $c$ is a large
absolute constant. Here we generalize and extend their local search algorithm
by considering larger and more sophisticated local search neighborhoods hence
allowing to swap multiple centers at the same time. Our algorithm achieves a $9
+ \varepsilon$ approximation ratio, which is the best possible for local
search. Importantly we show that our approach yields substantial practical
improvements, we show significant quality improvements over the approach of
Lattanzi and Sohler (ICML 2019) on several datasets.