Showing 2023Show all
2 papers · 1 filter
cs.CC2023
Complexity of Local Search for Euclidean Clustering Problems
Bodo Manthey, Nils Morawietz, Jesse van Rhijn +1
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for -Means cluste…
cs.DS2023
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Bodo Manthey, Jesse van Rhijn
We analyze the running time of the Hartigan-Wong method, an old algorithm for the -means clustering problem. First, we construct an instance on the line on which the method can…