Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NONDENSE INSTANCES:
Reports tagged with Nondense Instances:
TR06-101 | 22nd August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

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

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 >>>

ISSN 1433-8092 | Imprint