Department of Computer Science
 
Chair V

 
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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V