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

DOI10.1007/978-3-642-22006-7_15zbMATH Open1332.68072OpenAlexW1944873932MaRDI QIDQ3012803FDOQ3012803

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

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

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)

Cites Work

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

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
• Computing better approximate pure Nash equilibria in cut games via semidefinite programming
• Dynamics of Profit-Sharing Games
• 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)