Better balance by being biased: A 0.8776-approximation for max bisection
2013 (English)In: Proc Annu ACM SIAM Symp Discrete Algorithms, 2013, 277-294 p.Conference paper (Refereed)
Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the MAX BISECTION problem. We improve their algorithm to a 0.8776-approximation. As MAX BISECTION is hard to approximate within αGW + ∈ ≈ 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within αGW -∈, i.e., the bisection constraint (essentially) does not make MAX CUT harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of MAX 2-SAT. Our approximation ratio for this problem exactly matches the optimal approximation ratio for MAX 2-SAT, i.e., αLLZ + ∈ ≈ 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.
Place, publisher, year, edition, pages
2013. 277-294 p.
, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Approximation ratios, MAX CUT, Max-bisection, Optimal algorithm, Optimal approximation, Unique games conjecture, Optimization, Approximation algorithms
IdentifiersURN: urn:nbn:se:kth:diva-134648ScopusID: 2-s2.0-84876040323ISBN: 9781611972511OAI: oai:DiVA.org:kth-134648DiVA: diva2:678404
24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 6 January 2013 through 8 January 2013, New Orleans, LA
QC 201312122013-12-122013-11-272013-12-12Bibliographically approved