Lorenzo Beretta

Multi-Swap $k$-Means++

2023 · arXiv (Cornell University)

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 …