Research output per year
Research output per year
Bodo Manthey*, Jesse van Rhijn*
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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 language | English |
---|---|
Title of host publication | 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 |
Editors | Olaf Beyersdorff, Mamadou Moustapha Kante, Orna Kupferman, Daniel Lokshtanov |
Publisher | Dagstuhl |
ISBN (Electronic) | 9783959773119 |
DOIs | |
Publication status | Published - Mar 2024 |
Event | 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 - Clermont-Ferrand, France Duration: 12 Mar 2024 → 14 Mar 2024 Conference number: 41 |
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 289 |
ISSN (Print) | 1868-8969 |
Conference | 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 |
---|---|
Abbreviated title | STACS 2024 |
Country/Territory | France |
City | Clermont-Ferrand |
Period | 12/03/24 → 14/03/24 |
Research output: Working paper › Preprint › Academic