Complexity of Local Search for Euclidean Clustering Problems

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

doi:10.48550/arXiv.2312.14916

Complexity of Local Search for Euclidean Clustering Problems

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

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

100 Downloads (Pure)

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.

Original language	English
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2312.14916
Publication status	Published - 22 Dec 2023

Keywords

cs.CC
cs.DS

Access to Document

10.48550/arXiv.2312.14916Licence: CC BY

2312.14916v2Final published version, 917 KBLicence: CC BY

1 Conference contribution

Complexity of Local Search for Euclidean Clustering Problems
Manthey, B., Morawietz, N., van Rhijn, J. & Sommer, F., 4 Dec 2024, 35th International Symposium on Algorithms and Computation, ISAAC 2024. Mestre, J. & Wirth, A. (eds.). Dagstuhl, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 322).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
17 Downloads (Pure)

Cite this

@techreport{f27ce7ad11f7422aa193d8079841484c,

title = "Complexity of Local Search for Euclidean Clustering Problems",

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. ",

keywords = "cs.CC, cs.DS",

author = "Bodo Manthey and Nils Morawietz and {van Rhijn}, Jesse and Frank Sommer",

note = "33 pages, 4 figures",

year = "2023",

month = dec,

day = "22",

doi = "10.48550/arXiv.2312.14916",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Complexity of Local Search for Euclidean Clustering Problems

AU - Manthey, Bodo

AU - Morawietz, Nils

AU - van Rhijn, Jesse

AU - Sommer, Frank

N1 - 33 pages, 4 figures

PY - 2023/12/22

Y1 - 2023/12/22

N2 - 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.

AB - 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.

KW - cs.CC

KW - cs.DS

U2 - 10.48550/arXiv.2312.14916

DO - 10.48550/arXiv.2312.14916

M3 - Preprint

BT - Complexity of Local Search for Euclidean Clustering Problems

PB - ArXiv.org

ER -

Complexity of Local Search for Euclidean Clustering Problems

Abstract

Keywords

Access to Document

Fingerprint

Research output

Complexity of Local Search for Euclidean Clustering Problems

Cite this