Institut für Informatik
 
Abteilung V

 
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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V