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