## Abstract

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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |

Pages | 277-294 |

Number of pages | 18 |

Publication status | Published - 2013 |

MoE publication type | A4 Conference publication |

Event | ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country/Territory | United States |

City | New Orleans |

Period | 06/01/2013 → 08/01/2013 |