Sökning: WFRF:(Georgiou Konstantinos) >
Better Balance by B...
Better Balance by Being Biased : A 0.8776-Approximation for Max Bisection
-
- Austrin, Per (författare)
- KTH,Teoretisk datalogi, TCS
-
Benabbas, Siavosh (författare)
-
Georgiou, Konstantinos (författare)
-
(creator_code:org_t)
- 2016-10-10
- 2016
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : ASSOC COMPUTING MACHINERY. - 1549-6325 .- 1549-6333. ; 13:1
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering (hsv//eng)
Nyckelord
- Max-bisection
- approximation algorithms
- semidefinite programming
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas