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

2012/05/02 by Austrin, Per, Benabbas, Siavosh, Georgiou, Konstantinos
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1205.0458

Abstract

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.

Related

• MAX BISECTION might be harder to approximate than MAX CUT
• Separating MAX 2-AND, MAX DI-CUT and MAX CUT
• Tight approximability of MAX 2-SAT and relatives, under UGC
• An approximation algorithm for Maximum DiCut vs. Cut
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder