Multi-Swap Local Search for K-means: Dr. Lorenzo Beretta (Univ. of Copenhagen)
Speaker:
Dr. Lorenzo Beretta (Univ. of Copenhagen)
Data dell'evento:
Thursday, 11 May, 2023 - 15:00
Luogo:
DIAG - Aula Magna
Contatto:
Stefano Leonardi
Title: Multi-Swap Local Search for K-means.
Abstract: The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation.
Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a O(1)-approximation to the k-means clustering problem, where O(1) hides a large constant. Here we generalise their algorithm allowing it to swap multiple centers at the same time. Our algorithm achieves a 9 + epsilon approximation ratio, which is the best possible for local search. While the same approximation ratio can be achieved combining several known techniques, our algorithm is both asymptotically faster and more practical.
Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a O(1)-approximation to the k-means clustering problem, where O(1) hides a large constant. Here we generalise their algorithm allowing it to swap multiple centers at the same time. Our algorithm achieves a 9 + epsilon approximation ratio, which is the best possible for local search. While the same approximation ratio can be achieved combining several known techniques, our algorithm is both asymptotically faster and more practical.
gruppo di ricerca: