ECCC-Report TR06-101https://eccc.weizmann.ac.il/report/2006/101Comments and Revisions published for TR06-101en-usTue, 22 Aug 2006 16:45:39 +0300
Paper TR06-101
| Approximation Complexity of Nondense Instances of MAX-CUT |
Wenceslas Fernandez de la Vega,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2006/101We 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.
Tue, 22 Aug 2006 16:45:39 +0300https://eccc.weizmann.ac.il/report/2006/101