Settling the Complexity of Local Max-Cut (Almost) Completely
From MaRDI portal
Publication:3012803
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
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