Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-044 | 16th July 2002 00:00

A Polynomial Time Approximation Scheme for Subdense MAX-CUT

RSS-Feed

Abstract:

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-CSP) of the same average
density have PTASs. Our results display for the first time an existence
of PTASs for these subdense classes.



ISSN 1433-8092 | Imprint