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
2016 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 1, 2Article in journal (Refereed) Published
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 alpha(GW) + epsilon approximate to 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within alpha(GW) - epsilon, that is, that 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, that is, alpha(LLZ) + epsilon approximate to 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem from Raghavendra and Tan.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY , 2016. Vol. 13, no 1, 2
Keyword [en]
Max-bisection, approximation algorithms, semidefinite programming
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-202652DOI: 10.1145/2907052ISI: 000392927800002OAI: oai:DiVA.org:kth-202652DiVA: diva2:1078751
Note

QC 20170306

Available from: 2017-03-06 Created: 2017-03-06 Last updated: 2017-03-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Algorithms
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 16 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