Improved approximation of Max-Cut on graphs of bounded degree
From MaRDI portal
Publication:3150283
DOI10.1016/S0196-6774(02)00005-6zbMath1050.68110MaRDI QIDQ3150283
Michael Langberg, Uriel Feige, Marek Karpinski
Publication date: 30 September 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Maximum directed cuts in graphs with degree constraints ⋮ Affine reductions for LPs and SDPs ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ High-multiplicity cyclic job shop scheduling ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ On judicious bipartitions of graphs ⋮ Sparse graphs: Metrics and random models ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs
This page was built for publication: Improved approximation of Max-Cut on graphs of bounded degree
