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 $k$-Means cluste…