TR06-101 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski

Publication: 22nd August 2006 16:45

Downloads: 1683

Keywords:

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 approximate MAX-CUT.

On the other hand, we rule out existence of polynomial time approximation schemes (PTASs) for MAX-CUT instances with $\Omega(n^{2-\delta})$ edges for all $\delta>0$, under the standard complexity theoretic assumptions.