|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2002 | Copyright 2002 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |