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)).