Complexity of Local Search for Euclidean Clustering Problems
Lists
Only you see this
Abstract
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 clustering is PLS-complete, 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 $\mathcal{X} \subseteq \mathbb{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},
}