<div class="csl-bib-body">
<div class="csl-entry">Manthey, B., Morawietz, N., van Rhijn, J., & Sommer, F. (2024). Complexity of Local Search for Euclidean Clustering Problems. In J. Mestre & A. Wirth (Eds.), <i>35th International Symposium on Algorithms and Computation (ISAAC 2024)</i>. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2024.48</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/225532
-
dc.description.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.
en
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
flip-neighborhood
en
dc.subject
k-means
en
dc.subject
Local search
en
dc.subject
max cut
en
dc.subject
partitioning problem
en
dc.subject
PLS-complete
en
dc.title
Complexity of Local Search for Euclidean Clustering Problems
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
University of Twente, Netherlands (the)
-
dc.contributor.affiliation
Friedrich Schiller University Jena, Germany
-
dc.contributor.affiliation
University of Twente, Netherlands (the)
-
dc.contributor.editoraffiliation
The University of Sydney, Australia
-
dc.contributor.editoraffiliation
The University of Sydney, Australia
-
dc.relation.isbn
978-3-95977-354-6
-
dc.relation.issn
1868-8969
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
35th International Symposium on Algorithms and Computation (ISAAC 2024)
-
tuw.container.volume
322
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPIcs.ISAAC.2024.48
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0000-0001-6278-5059
-
tuw.author.orcid
0000-0002-7283-4982
-
tuw.author.orcid
0000-0002-3416-7672
-
tuw.event.name
35th International Symposium on Algorithms and Computation (ISAAC 2024)
en
tuw.event.startdate
08-12-2024
-
tuw.event.enddate
11-12-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Sydney
-
tuw.event.country
AU
-
tuw.event.presenter
Manthey, Bodo
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
crisitem.author.dept
University of Twente, Netherlands (the)
-
crisitem.author.dept
Friedrich Schiller University Jena, Germany
-
crisitem.author.dept
University of Twente, Netherlands (the)
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
