Per Austrin: Better balance by being biased: a 0.8776-algorithm for Max Bisection
Per Austrin, University of Toronto
Tid: Ti 2012-04-03 kl 13.15
Plats: Room 1537, Lindstedtsvägen 3, KTH CSC
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 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.)