Towards explaining the speed of k-means

Research output: Contribution to journalArticleProfessional

13 Downloads (Pure)

Abstract

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
Volume2011
Publication statusPublished - 2011

Keywords

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

Cite this

@article{47a8e718c2be42008f856307ee1c523b,
title = "Towards explaining the speed of k-means",
abstract = "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.",
keywords = "Smoothed Analysis, k-Means method, IR-79466, Clustering, METIS-285231, EWI-21249",
author = "Bodo Manthey and {van de Pol}, {Jan Cornelis} and F. Raamsdonk and Stoelinga, {Mari{\"e}lle Ida Antoinette}",
year = "2011",
language = "Undefined",
volume = "2011",
pages = "45--54",
journal = "Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica",

}

TY - JOUR

T1 - Towards explaining the speed of k-means

AU - Manthey, Bodo

A2 - van de Pol, Jan Cornelis

A2 - Raamsdonk, F.

A2 - Stoelinga, Mariëlle Ida Antoinette

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Smoothed Analysis

KW - k-Means method

KW - IR-79466

KW - Clustering

KW - METIS-285231

KW - EWI-21249

M3 - Article

VL - 2011

SP - 45

EP - 54

JO - Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica

JF - Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica

ER -