Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem

DOI10.1007/978-3-662-48350-3_43zbMath1369.68239OpenAlexW2295408917MaRDI QIDQ3452814

Heiko Röglin, Michael Etscheid

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• A local search approximation algorithm for \(k\)-means clustering
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Settling the Complexity of Local Max-Cut (Almost) Completely
• Clustering for edge-cost minimization (extended abstract)
• Simple Local Search Problems that are Hard to Solve
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Smoothed analysis of algorithms
• Smoothed Analysis of Local Search for the Maximum-Cut Problem
• Smoothed Analysis of the k-Means Method

This page was built for publication: Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem