Manthey, Bodo; id_orcid 0000-0001-6278-5059

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