k-Means has polynomial smoothed complexity


Arthur, David and Manthey, Bodo and Röglin, Heiko (2009) k-Means has polynomial smoothed complexity. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, 24-27 Oct 2009, Atlanta, GA, USA (pp. pp. 405-414).

open access
Abstract: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.
Item Type:Conference or Workshop Item
Copyright:© 2009 IEEE
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/70194
Official URL:http://doi.ieeecomputersociety.org/10.1109/FOCS.2009.14
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page