Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
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
Identifiers
URN: urn:nbn:se:kth:diva-134648Scopus ID: 2-s2.0-84876040323ISBN: 9781611972511 (print)OAI: oai:DiVA.org:kth-134648DiVA: diva2:678404
Conference
24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 6 January 2013 through 8 January 2013, New Orleans, LA
Note

QC 20131212

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

Open Access in DiVA

No full text

Scopus

Authority records BETA

Austrin, Per

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 96 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf