Better balance by being biased: A 0.8776-approximation for max bisection

Per Austrin*, Siavosh Benabbas, Konstantinos Georgiou

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

17 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Sivut277-294
Sivumäärä18
TilaJulkaistu - 2013
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM-SIAM Symposium on Discrete Algorithms - New Orleans, Yhdysvallat
Kesto: 6 tammikuuta 20138 tammikuuta 2013
Konferenssinumero: 24

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
LyhennettäSODA
MaaYhdysvallat
KaupunkiNew Orleans
Ajanjakso06/01/201308/01/2013

Sormenjälki

Sukella tutkimusaiheisiin 'Better balance by being biased: A 0.8776-approximation for max bisection'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä