# 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.