Towards explaining the speed of k-means
Bodo Manthey, Jaco van de Pol, Femke van Raamsdonk, Mariëlle I. A. Stoelinga · University of Twente Research Information · 2011
The $k$-means method is a popular algorithm for clustering, known for its speed in practice. This stands in contrast to its exponential worst-case running-time. To explain the speed of the $k$-means method, a smoothed analysis has been conducted. We sketch this smoothed analysis and a generalization to Bregman divergences.