Improved approximation of Max-Cut on graphs of bounded degree

DOI10.1016/S0196-6774(02)00005-6MaRDI QIDQ3150283zbMATH OpenFDO

Authors Michael Langberg, Marek Karpinski, Uriel Feige

Publication date 30 September 2002

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0196-6774(02)00005-6

zbMATH Keywords

Max-Cut problemrandom hyperplane rounding techniquesemidefinite relaxation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• MAX CUT in cubic graphs
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations

Cited in

(29)

• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Affine reductions for LPs and SDPs
• Approximating graph-constrained max-cut
• Maximum directed cuts in graphs with degree constraints
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Triangle-free subcubic graphs with minimum bipartite density
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• MAX CUT in cubic graphs
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• scientific article; zbMATH DE number 6987353 (Why is no real title available?)
• scientific article; zbMATH DE number 2140434 (Why is no real title available?)
• An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
• MAX-CUT has a randomized approximation scheme in dense graphs
• Sparse graphs: metrics and random models
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• On judicious bipartitions of graphs
• Local approximation of the maximum cut in regular graphs
• Local approximation of the maximum cut in regular graphs
• Local improving algorithms for large cuts in graphs with maximum degree three
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Theoretical approximation ratios for warm-started QAOA on 3-regular max-cut instances at depth p = 1
• An improved approximation algorithm for hypergraph max p-section
• Triangles improve 0.878 approximation for Maxcut
• An improved SDP rounding approximation algorithm for the max hypergraph bisection
• High-multiplicity cyclic job shop scheduling

This page was built for publication: Improved approximation of Max-Cut on graphs of bounded degree

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