Towards explaining the speed of k-means

Research output: Contribution to journalArticleProfessional

85 Downloads (Pure)


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.
Original languageUndefined
Pages (from-to)45-54
Number of pages10
JournalNieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica
Publication statusPublished - 2011


  • Smoothed Analysis
  • k-Means method
  • IR-79466
  • Clustering
  • METIS-285231
  • EWI-21249

Cite this