Complexity of local search for Euclidean clustering problems

DOI10.4230/LIPICS.ISAAC.2024.48MaRDI QIDQ7260668zbMATH OpenFDO

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

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.48

zbMATH Keywords

\(k\)-meansflip-neighborhoodlocal searchmax cutpartitioning problemPLS-complete

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• k-means requires exponentially many iterations even in the plane
• A PRG for Lipschitz functions of polynomials with applications to sparsest cut
• Algorithm AS 136: A K-Means Clustering Algorithm
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Efficient Heuristic Procedure for Partitioning Graphs
• Clustering for edge-cost minimization (extended abstract)
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• Complexity of the weighted max-cut in Euclidean space
• Expander flows, geometric embeddings and graph partitioning
• Finding 3-swap-optimal independent sets and dominating sets is hard
• Grouping Multidimensional Data
• How easy is local search?
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• scientific article; zbMATH DE number 1973378 (Why is no real title available?)
• Improving the Smoothed Complexity of FLIP for Max Cut Problems
• Least squares quantization in PCM
• Local max-cut in smoothed polynomial time
• Metric spaces and positive definite functions.
• NP-hardness of Euclidean sum-of-squares clustering
• On approximate geometric \(k\)-clustering
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• Settling the complexity of local max-cut (almost) completely
• Simple Local Search Problems that are Hard to Solve
• Smoothed analysis of local search for the maximum-cut problem
• Smoothed analysis of the k-means method
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Smoothed complexity of local max-cut and binary max-CSP
• Sparsest cuts and bottlenecks in graphs
• The k-Opt algorithm for the traveling salesman problem has exponential running time for k 5
• The complexity of the \texttt{k-means} method
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
• The planar \(k\)-means problem is NP-hard
• Theoretical aspects of local search.
• Worst-case and smoothed analysis of the hartigan-Wong method for k-means clustering

This page was built for publication: Complexity of local search for Euclidean clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260668)