Subexponential LPs Approximate Max-Cut
share
We show that for every ε > 0, the degree-n^ε Sherali-Adams linear program (with (Õ(n^ε)) variables and constraints) approximates the maximum cut problem within a factor of (1/2+ε'), for some ε'(ε) > 0. Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut, and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to 1/2 (up to the function ε'(ε)). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than 1/2 for Max-Cut in time 2^o(n). We also separate the power of Sherali-Adams versus Lovasz-Schrijver hierarchies for approximating Max-Cut, since it is known that (1/2+ε) approximation of Max Cut requires Ω_ε (n) rounds in the Lovasz-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem: we show that for every ε > 0 the degree-n^εlog q) Sherali-Adams linear program distinguishes instances of Unique Games of value ≥ 1-ε' from instances of value ≤ε', for some ε'( ε) >0, where q is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques.
READ FULL TEXT