|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-APX-Reports 2002 | Copyright 2002 Universität Bonn, Institut für Informatik, Abt. V | |
|
8981 July 16, 2002 |
A Polynomial Time Approximation Scheme for Subdense MAX-CUT
W. Fernandez de la Vega and Marek Karpinski [Download PostScript] [Download PDF] We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-2CSP) of the same average density have PTASs. Our results display for the first time an existence of PTASs for these subdense classes. |
|
|
Last Change:
11/05/14 at 10:24:39
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |