Complexity of Local Search for Euclidean Clustering Problems

Autor:	Manthey, Bodo, Morawietz, Nils, van Rhijn, Jesse, Sommer, Frank
Rok vydání:	2023
Předmět:	Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: 33 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2312.14916 Zobrazit plný text záznamu View this record from Arxiv