Settling the complexity of local max-cut (almost) completely

DOI10.1007/978-3-642-22006-7_15MaRDI QIDQ3012803zbMATH OpenOpenAlexFDO

Authors Robert Elsässer, Tobias Tscheuschner

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_15

zbMATH Keywords

graphslocal searchsmoothed complexityPLSMax-Cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• Integer Linear Programs and Local Search for Max-Cut
• Improving the smoothed complexity of FLIP for max cut problems
• Local max-cut in smoothed polynomial time
• Smoothed analysis of local search for the maximum-cut problem

Cites work

• scientific article; zbMATH DE number 176747 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2119754 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• Computing Stable Outcomes in Hedonic Games
• How easy is local search?
• Integer Linear Programs and Local Search for Max-Cut
• Local search: simple, successful, but sometimes sluggish
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• On the impact of combinatorial structure on congestion games
• Simple Local Search Problems that are Hard to Solve
• Smoothed analysis of algorithms
• Smoothed analysis of integer programming
• The complexity of pure Nash equilibria
• Typical properties of winners and losers in discrete optimization
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• k-Means Has Polynomial Smoothed Complexity

Cited in

(15)

• Local improving algorithms for large cuts in graphs with maximum degree three
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Improving the smoothed complexity of FLIP for max cut problems
• Integer Linear Programs and Local Search for Max-Cut
• Smoothed analysis of local search for the maximum-cut problem
• Smoothed complexity of local max-cut and binary max-CSP
• Computational methods for solving nonconvex block-separable constrained quadratic problems
• Local max-cut in smoothed polynomial time
• Partitioning problems via random processes
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Dynamics of Profit-Sharing Games
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
• Smoothed analysis of local search algorithms

This page was built for publication: Settling the complexity of local max-cut (almost) completely

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