A Polynomial Time Approximation Scheme for Subdense MAX-CUT

Wenceslas Fernandez de la Vega; Marek Karpinski

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR02-044 | 16th July 2002 00:00

A Polynomial Time Approximation Scheme for Subdense MAX-CUT

TR02-044 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 16th July 2002 13:46
Downloads: 2751

Keywords:

Approximation Algorithms, MAX-CSP, Max-Cut, NP-hardness, Polynomial Time Approximation Schemes, Subdense Instances

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