Better balance by being biased: A 0.8776-approximation for max bisection

Per Austrin*, Siavosh Benabbas, Konstantinos Georgiou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

18 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Number of pages18
Publication statusPublished - 2013
MoE publication typeA4 Conference publication
EventACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
Conference number: 24


ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
Country/TerritoryUnited States
CityNew Orleans


Dive into the research topics of 'Better balance by being biased: A 0.8776-approximation for max bisection'. Together they form a unique fingerprint.

Cite this