# Computational Complexity - Research Seminar

## Bodo Manthey: *k-Means has Polynomial Smoothed Complexity*

May 28, 2009, 10:15 a.m.

E 1 3, Room 415

The *k*-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the *k*-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number *n* of data points.

We settle the smoothed running time of the *k*-means method. We show that the smoothed number of iterations is bounded by a polynomial in *n* and 1/σ, where σ is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the *k*-means method will run in expected polynomial time on that input set.