2026-07-25T02:34:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22175 2024-12-04T06:53:45Z ddc:004 open_access

Complexity of Local Search for Euclidean Clustering Problems Manthey, Bodo Morawietz, Nils van Rhijn, Jesse Sommer, Frank Local search PLS-complete max cut k-means partitioning problem flip-neighborhood 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bodo Manthey and Nils Morawietz and Jesse van Rhijn and Frank Sommer 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.48 urn:nbn:de:0030-drops-221755 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.48 eng https://creativecommons.org/licenses/by/4.0/legalcode