Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 10, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Ola Svensson (EPFL)
For quite some time the best approximation algorithm for k-means has been 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 (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics.
Automatic MiSe System Software Version 1.4803M | admin login