Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

DOI10.1137/1.9781611973105.21zbMath1422.68284arXiv1205.0458OpenAlexW2952933284MaRDI QIDQ5741729

Konstantinos Georgiou, Siavosh Benabbas, Per Austrin

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.0458

Mathematics Subject Classification ID

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

Related Items (10)

Complexity of approximating CSP with balance/hard constraints ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ On bisections of graphs without complete bipartite graphs ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Better approximation algorithms for influence maximization in online social networks ⋮ Speeding up a memetic algorithm for the max-bisection problem ⋮ An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems

This page was built for publication: Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection