We prove that the subdense instances of MAX-CUT of average
degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS).
We extend this result also to show that the instances of general 2-ary
maximum constraint satisfaction problems (MAX-CSP) of the same average
density have PTASs. Our results ... more >>>

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>