Pierluigi Crescenzi and Luca Trevisan.
MAXNP-completeness Made Easy.
Submitted, December 1996.
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 MAXNP-completeness of MAX3SAT 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)).