Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-039 | 11th September 1997 00:00

MAX NP-Completeness Made Easy

RSS-Feed

Abstract:

We introduce a simple technique to obtain reductions
between optimization constraint satisfaction problems. The
technique uses the probabilistic method to reduce the size of
disjunctions. As a first application, we prove the
MAX NP-completeness of MAX 3SAT without using the PCP theorem
(thus solving an open question posed in Khanna et al. (1994)).
Successively, we show that the ``planar'' restrictions of
several optimization constraint satisfaction problems admit
linear-time approximation schemes (thus improving the results
of Khanna and Motwani (1996)).



ISSN 1433-8092 | Imprint