Pierluigi Crescenzi and Luca Trevisan.<br>
<b>MAXNP-completeness Made Easy.</b><br>
Submitted, December 1996.<br>

<dl>

<dt> <b> Abstract</b> <dd>
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)).
</dl>