Complexity of Local Search for Euclidean Clustering Problems

Bodo Manthey, Nils Morawietz, Jesse van Rhijn, Frank Sommer

Abstract

We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-hard. First, we show that the Hartigan-Wong method, which is essentially the Flip heuristic, for k-Means clustering is PLS-hard, even when k = 2. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set 𝒳 ⊆ R^d; a problem which is equivalent to Min Sum 2-Clustering.
BibTeX
@inproceedings{manthey2024complexity,
  author = {Bodo Manthey and Nils Morawietz and Jesse van Rhijn and Frank Sommer},
  title = {{Complexity of Local Search for Euclidean Clustering Problems}},
  booktitle = {ISAAC},
  year = {2024},
  doi = {10.4230/lipics.isaac.2024.48},
}
Figure