Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering

Bodo Manthey*, Jesse van Rhijn*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

44 Downloads (Pure)

Abstract

We analyze the running time of the Hartigan-Wong method, an old algorithm for the k-means clustering problem. First, we construct an instance on the line on which the method can take 2Ω(n) steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when k-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of n points in d dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by k12kd·poly(n,k,d,1/σ) when the points in the instance are perturbed by independent d-dimensional Gaussian random variables of mean 0 and standard deviation σ.

Original languageEnglish
Title of host publication41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
EditorsOlaf Beyersdorff, Mamadou Moustapha Kante, Orna Kupferman, Daniel Lokshtanov
PublisherDagstuhl
ISBN (Electronic)9783959773119
DOIs
Publication statusPublished - Mar 2024
Event41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 - Clermont-Ferrand, France
Duration: 12 Mar 202414 Mar 2024
Conference number: 41

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume289
ISSN (Print)1868-8969

Conference

Conference41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
Abbreviated titleSTACS 2024
Country/TerritoryFrance
CityClermont-Ferrand
Period12/03/2414/03/24

Keywords

  • Heuristics
  • k-Means clustering
  • Local search
  • Probabilistic analysis
  • Smoothed analysis

Fingerprint

Dive into the research topics of 'Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering'. Together they form a unique fingerprint.

Cite this