A note on approximating Max-Bisection on regular graphs

DOI10.1016/S0020-0190(00)00189-7zbMATH Open1032.68119MaRDI QIDQ1603473FDOQ1603473

Authors: Marek Karpinski, Michael Langberg, Uriel Feige 

Publication date: 14 July 2002

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

zbMATH Keywords

Approximation algorithmsSemidefinite programmingMax-BisectionRegular graphsMax-Cut

Mathematics Subject Classification ID

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

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• The number of matchings in random regular graphs and bipartite graphs

Cited In (7)

• Approximation and complexity of the capacitated geometric median problem
• 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
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• A note on edge-based graph partitioning and its linear algebraic structure
• Bounds on the bisection width for random \(d\)-regular graphs

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)