A note on approximating Max-Bisection on regular graphs
From MaRDI portal
Publication:1603473
DOI10.1016/S0020-0190(00)00189-7zbMath1032.68119MaRDI QIDQ1603473
Michael Langberg, Marek Karpinski, Uriel Feige
Publication date: 14 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (7)
Bounds on the max and min bisection of random cubic and random 4-regular graphs ⋮ Bounds on the bisection width for random \(d\)-regular graphs ⋮ A note on edge-based graph partitioning and its linear algebraic structure ⋮ An improved kernel for max-bisection above tight lower bound ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Speeding up a memetic algorithm for the max-bisection problem ⋮ Approximation and complexity of the capacitated geometric median problem
Cites Work
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The number of matchings in random regular graphs and bipartite graphs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Probability Inequalities for Sums of Bounded Random Variables
- Unnamed Item
This page was built for publication: A note on approximating Max-Bisection on regular graphs
