van Rhijn, Jesse; id_orcid 0000-0002-3416-7672

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

2024 · University of Twente Research Information

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, …