Pierluigi Crescenzi and Luca Trevisan.
MAXNPcompleteness 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 MAXNPcompleteness 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 lineartime approximation schemes (thus improving the results of
Khanna and Motwani (1996)).