Better balance by being biased: a 0.8776-algorithm for Max Bisection
|Affiliation:||University of Toronto|
|Room:||Mathematics & Computer Building (MC) 5158|
Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection is hard to approximate within roughly 0.8786 (under the Unique Games Conjecture) our algorithm is very nearly optimal.
We also obtain an improved algorithm for the analogous variant of Max 2-Sat. Our approximation ratio for this problem exactly matches the optimal (assuming the UGC) ratio of roughly 0.9401 for Max 2-Sat, showing that the bisection constraint does not make Max 2-Sat harder.
(Joint work with Siavosh Benabbas and Konstantinos Georgiou.)
200 University Avenue West
Waterloo, ON N2L 3G1