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
Association for Computing Machinery (ACM), 2016. Vol. 13, no 1, 2
Keyword [en]
Max-bisection, approximation algorithms, semidefinite programming
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-202784DOI: 10.1145/2907052ISI: 000392927800002OAI: oai:DiVA.org:kth-202784DiVA: diva2:1079073
Note

QC 20170307

Available from: 2017-03-07 Created: 2017-03-07 Last updated: 2017-11-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Algorithms
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 28 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