Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Bodo Manthey: Smoothed Analysis of k-Means Clustering

April 22, 2008, 10:15 a.m.
E 1 3, Room 415

We introduce Lloyd's algorithm for k-means clustering as a way to cluster data points in some high-dimensional space. This algorithm works well in practice, but its worst-case running-time is exponential in the dimension d of the space. David Arthur and Sergei Vassilvitskii (Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method, FOCS 2006) have provided a smoothed analysis of k-means clustering that shows that, after perturbation, the running-time is only exponential in k.

We highlight the ideas behind the analysis of k-means and point out some topics for further research.