  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.
  In this paper, 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/\sigma, where \sigma 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.
