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 article, 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.
['David Arthur', 'Bodo Manthey', 'Heiko Röglin']
Smoothed Analysis of the k-Means Method