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

Per Austrin; Siavosh Benabbas; Konstantinos Georgiou

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

Per Austrin^*
, Siavosh Benabbas
, Konstantinos Georgiou

^*Corresponding author for this work

Department of Computer Science

KTH Royal Institute of Technology
University of Toronto
University of Waterloo

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

19 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 language	English
Title of host publication	Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Pages	277-294
Number of pages	18
Publication status	Published - 2013
MoE publication type	A4 Conference publication
Event	ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24

Conference

Conference	ACM-SIAM Symposium on Discrete Algorithms
Abbreviated title	SODA
Country/Territory	United States
City	New Orleans
Period	06/01/2013 → 08/01/2013

Cite this

@inproceedings{201f5157e9f24a8b977a2054cc613363,

title = "Better balance by being biased: A 0.8776-approximation for max bisection",

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.",

author = "Per Austrin and Siavosh Benabbas and Konstantinos Georgiou",

year = "2013",

language = "English",

isbn = "9781611972511",

pages = "277--294",

booktitle = "Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013",

note = "ACM-SIAM Symposium on Discrete Algorithms, SODA ; Conference date: 06-01-2013 Through 08-01-2013",

}

TY - GEN

T1 - Better balance by being biased

T2 - ACM-SIAM Symposium on Discrete Algorithms

AU - Austrin, Per

AU - Benabbas, Siavosh

AU - Georgiou, Konstantinos

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84876040323

M3 - Conference article in proceedings

AN - SCOPUS:84876040323

SN - 9781611972511

SP - 277

EP - 294

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -

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

Abstract

Conference

Other files and links

Fingerprint

Cite this