School of Mathematical Sciences

Improved approximation for K-means in arbitrary dimension menu

Improved approximation for K-means in arbitrary dimension

Justin Ward (QMUL)
Fri, 06/10/2017 - 16:00
W316, Queen's Building
Seminar series: 

In the general 'K-means problem', we are given n input points in a Euclidean space and seek to find k "center" points in the space so that the sum of the squared distances of each input point to its nearest center is minimized. While there have been several recent results for the special case in which the Euclidean space has some bounded dimension d, the best known approximation in arbitrary Euclidean spaces has remained (9+\epsilon) since 2002. In this talk I will present a new algorithm that achieves a 6.36-approximation for this problem, as well as an improved 2.64 approximation for the Euclidean k-median problem. The algorithm is based on a new Lagrangian multiplier preserving primal dual approach. This talk is based on joint work with Sara Ahmadian, Ashkan Norouzi-Fard, and Ola Svensson (to appear in FOCS '17).