Complexity of Local Search for Euclidean Clustering Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908354799992832 |
|---|---|
| author | Manthey, Bodo Morawietz, Nils van Rhijn, Jesse Sommer, Frank |
| author_facet | Manthey, Bodo Morawietz, Nils van Rhijn, Jesse Sommer, Frank |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14916 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity of Local Search for Euclidean Clustering Problems Manthey, Bodo Morawietz, Nils van Rhijn, Jesse Sommer, Frank Computational Complexity Data Structures and Algorithms 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. |
| title | Complexity of Local Search for Euclidean Clustering Problems |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.14916 |