For quite some time the best approximation algorithm for k-means were a simple local search heuristic yielding an approximation guarantee of 9, a ratio that is known to be tight with respect to such methods.
In this talk, we present an improved guarantee of 6.357 via a new primal-dual approach that allows us to exploit the geometric structure of k-means.
Finally, we also consider the semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we should that few queries are sufficient to recover a clustering that is arbitrarily close to the optimal one.
This is based on joint works with Sara Ahmadian, Buddhima Gamlath, Ashkan Norouzi-Fard, and Justin Ward.
25/06/2019
3pm, room G50, 3rd floor, building G (viale Regina Elena 295/B)
Ola Svensson is an Associate Professor at the School of Computer and Communication Sciences at EPFL, Switzerland. He is interested in theoretical aspects of computer science with an emphasis on the approximability of NP-hard optimization problems. His work has received several recognitions including the 2019 Michael and Sheila Held Prize by the National Academy of Sciences and best paper awards at FOCS and STOC.