Approximation Complexity of Nondense Instances of MAX-CUT
Wenceslas Fernandez de la Vega, Marek Karpiński · Electronic colloquium on computational complexity · 2006
We prove existence of approximation schemes for instances of MAXCUT with ( n � ) edges which work in O ( � 2 ) n O(1) time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with ( n polylogn ) edges. The result depends on new sampling method for smoothed linear programs that approximate MAX-CUT. On the other hand, we rule out existence of polynomial time approximation schemes (PTASs) for MAX-CUT instances with (n � ) edges for all � > 0, under the standard complexity theoretic assumptions.