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 contributionScientificpeer-review

17 Citations (Scopus)

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.

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

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CityNew Orleans
Period06/01/201308/01/2013

Fingerprint

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