Smoothed Analysis of Local Search for the Maximum-Cut Problem

DOI10.1145/3011870zbMath1421.68152OpenAlexW3160805239WikidataQ105584191 ScholiaQ105584191MaRDI QIDQ4962657

Heiko Röglin, Michael Etscheid

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3011870

zbMATH Keywords

local searchsmoothed analysismaximum-cut problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (5)

Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ Smoothed analysis for tensor methods in unsupervised learning ⋮ Smoothing the Gap Between NP and ER ⋮ Phase transition of degeneracy in minor-closed families ⋮ Local optima of the Sherrington-Kirkpatrick Hamiltonian

This page was built for publication: Smoothed Analysis of Local Search for the Maximum-Cut Problem