Record link: 
http://hdl.handle.net/20.500.12708/225532
-
Title: 
Complexity of Local Search for Euclidean Clustering Problems
en
Citation: 
Manthey, B., Morawietz, N., van Rhijn, J., & Sommer, F. (2024). Complexity of Local Search for Euclidean Clustering Problems. In J. Mestre & A. Wirth (Eds.), 35th International Symposium on Algorithms and Computation (ISAAC 2024). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2024.48
-
Publisher DOI: 
10.4230/LIPIcs.ISAAC.2024.48
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Manthey, Bodo 
Morawietz, Nils 
van Rhijn, Jesse 
Sommer, Frank 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
35th International Symposium on Algorithms and Computation (ISAAC 2024) 
-
ISBN: 
978-3-95977-354-6
-
Volume: 
322
-
Date (published): 
4-Dec-2024
-
Event name: 
35th International Symposium on Algorithms and Computation (ISAAC 2024) 
en
Event date: 
8-Dec-2024 - 11-Dec-2024
-
Event place: 
Sydney, Australia
-
Number of Pages: 
16
-
Publisher: 
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
Peer reviewed: 
Yes
-
Keywords: 
flip-neighborhood; k-means; Local search; max cut; partitioning problem; PLS-complete
en
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
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

8
checked on Jan 26, 2026

Google ScholarTM

Check