Settling the Complexity of Local Max-Cut (Almost) Completely

DOI10.1007/978-3-642-22006-7_15zbMath1332.68072OpenAlexW1944873932MaRDI QIDQ3012803

Tobias Tscheuschner, Robert Elsässer

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

local searchgraphsPLSsmoothed complexityMax-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)

Related Items (5)

Smoothed Analysis of Local Search Algorithms ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ Dynamics of Profit-Sharing Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed analysis of integer programming
• How easy is local search?
• Computing Stable Outcomes in Hedonic Games
• Simple Local Search Problems that are Hard to Solve
• On the impact of combinatorial structure on congestion games
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• The complexity of pure Nash equilibria
• Typical properties of winners and losers in discrete optimization
• Smoothed analysis of algorithms
• Local Search: Simple, Successful, But Sometimes Sluggish
• Integer Linear Programs and Local Search for Max-Cut
• k-Means Has Polynomial Smoothed Complexity

This page was built for publication: Settling the Complexity of Local Max-Cut (Almost) Completely