Change search
ReferencesLink to record
Permanent link

Direct link
Better balance by being biased: A 0.8776-approximation for max bisection
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
2013 (English)In: Proc Annu ACM SIAM Symp Discrete Algorithms, 2013, 277-294 p.Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
Approximation ratios, MAX CUT, Max-bisection, Optimal algorithm, Optimal approximation, Unique games conjecture, Optimization, Approximation algorithms
National Category
Computer Science
URN: urn:nbn:se:kth:diva-134648ScopusID: 2-s2.0-84876040323ISBN: 9781611972511OAI: diva2:678404
24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 6 January 2013 through 8 January 2013, New Orleans, LA

QC 20131212

Available from: 2013-12-12 Created: 2013-11-27 Last updated: 2013-12-12Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 35 hits
ReferencesLink to record
Permanent link

Direct link