Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
From MaRDI portal
Publication:5741729
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
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