Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-101 | 22nd August 2006 00:00

#### Approximation Complexity of Nondense Instances of MAX-CUT

TR06-101
Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 22nd August 2006 16:45
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.