Recently, Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the M ax B isection problem. We improve their algorithm to a 0.8776-approximation. As M ax B isection is hard to approximate within α GW + ε ≈ 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that M ax B isection is approximable within α GW − ε, that is, that the bisection constraint (essentially) does not make M ax C ut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of M ax 2-S at . Our approximation ratio for this problem exactly matches the optimal approximation ratio for M ax 2-S at , that is, α LLZ + ε ≈ 0.9401, showing that the bisection constraint does not make M ax 2-S at harder. This improves on a 0.93-approximation for this problem from Raghavendra and Tan.

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 \approx 0.8786$ under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that Max Bisection is approximable within $\alpha_{GW}-\epsilon$, 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., $\alpha_{LLZ} + \epsilon \approx 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.

We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.