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.
|Number of pages||10|
|Journal||Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica|
|Publication status||Published - 2011|
- Smoothed Analysis
- k-Means method