Smoothed Analysis of Local Search for the Maximum-Cut Problem

DOI10.1137/1.9781611973402.66MaRDI QIDQ5384027zbMATH OpenOpenAlexFDO

Authors Michael Etscheid, Heiko Röglin

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.66

Mathematics Subject Classification ID

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

Recommendations

• Smoothed analysis of local search for the maximum-cut problem
• Local max-cut in smoothed polynomial time
• Smoothed complexity of local max-cut and binary max-CSP
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Smoothed analysis of local search algorithms
• Smoothed Analysis of Local Search
• An efficient Lagrangian smoothing heuristic for max-cut
• Lagrangian smoothing heuristics for Max-cut
• A local search approximation algorithm for the multiway cut problem
• Smoothed Performance Guarantees for Local Search

Cited in

(9)

• Smoothed Performance Guarantees for Local Search
• Smoothed analysis of local search algorithms
• Smoothed analysis of the squared Euclidean maximum-cut problem
• On percolation and \(\mathcal{NP}\)-hardness
• Smoothed analysis of local search for the maximum-cut problem
• Local max-cut in smoothed polynomial time
• Smoothed Analysis of Local Search
• Smoothed complexity of local max-cut and binary max-CSP
• Experimental evaluation of a local search approximation algorithm for the multiway cut problem

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

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