MAX NP-COMPLETENESS MADE EASY

We introduce a simple technique to obtain reductions between optimization constraint satisfaction problems with respect to an approximation preserving reducibility more powerful than the commonly used L-reducibility. The technique applies 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).