Smoothed Analysis of Local Search for the Maximum-Cut Problem

DOI10.1145/3011870zbMath1421.68152WikidataQ105584191 ScholiaQ105584191MaRDI QIDQ4962657

Michael Etscheid, Heiko Röglin

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 search; smoothed analysis; maximum-cut problem

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C59: Approximation methods and heuristics in mathematical programming

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)