22.08.2006

We prove existence of approximation schemes for instances of MAX-CUTwith Ω(n²/Δ) edges which work in2^O∼(Δ/ε2)n^O(1) time.This entails in particular existence of quasi-polynomialapproximation schemes (QPTASs) for mildly sparse instances ofMAX-CUT with Ω(n²/polylog n) edges.The result depends on new sampling method for smoothedlinear programs that approximate MAX-CUT.
On the other hand, we rule out existence of polynomial timeapproximation schemes (PTASs) for MAX-CUT instances withΩ(n^2-δ) edges for all δ > 0, under the standardcomplexity theoretic assumptions.