A note on approximating Max-Bisection on regular graphs

DOI10.1016/S0020-0190(00)00189-7MaRDI QIDQ1603473zbMATH OpenFDO

Authors Marek Karpinski, Michael Langberg, Uriel Feige

Publication date 14 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(00)00189-7

zbMATH Keywords

Approximation algorithmsMax-BisectionMax-CutRegular graphsSemidefinite programming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Probability Inequalities for Sums of Bounded Random Variables
• The number of matchings in random regular graphs and bipartite graphs

Cited in

(10)

• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• An improved kernel for max-bisection above tight lower bound
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Approximation and complexity of the capacitated geometric median problem
• Speeding up a memetic algorithm for the max-bisection problem
• Bounds on the bisection width for random \(d\)-regular graphs
• A note on edge-based graph partitioning and its linear algebraic structure
• An improved approximation algorithm for hypergraph max p-section
• Max-Cut with multiple cardinality constraints
• An improved SDP rounding approximation algorithm for the max hypergraph bisection

This page was built for publication: A note on approximating Max-Bisection on regular graphs

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