Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2006 Copyright 2006 Universität Bonn, Institut für Informatik, Abt. V
85276

22.08.2006

Approximation Complexity of Nondense Instances of MAX-CUT
W. Fernandez de la Vega and Marek Karpinski
[Download PostScript] [Download PDF]

We prove existence of approximation schemes for instances of MAX-CUTwith Ω(n2/Δ) edges which work in2O(Δ/ε2)nO(1) time.This entails in particular existence of quasi-polynomialapproximation schemes (QPTASs) for mildly sparse instances ofMAX-CUT with Ω(n2/polylog n) edges.The result depends on new sampling method for smoothedlinear programs that approximate MAX-CUT.
On the other hand, we rule out existence of polynomial timeapproximation schemes (PTASs) for MAX-CUT instances withΩ(n2-δ) edges for all δ > 0, under the standardcomplexity theoretic assumptions.

Last Change: 11/05/14 at 10:36:11
 English
Universität Bonn -> Institut für Informatik -> Abteilung V