On Syntactic versus Computational Views of Approximability

We attempt to reconcile the two distinct views of approximation classes: {\em syntactic} and {\em computational}. Syntactic classes such as MAX SNP allow for clean complexity-theoretic results and natural complete problems, while computational classes such as APX allow us to work with problems whose approximability is well-understood. Our results give a computational framework for studying syntactic classes, and provide a syntactic characterization of computational classes, as follows. We compare the syntactically defined class $\msnp$ with the computationally defined class APX and show that every problem in APX can be ``placed'' (i.e., L-reduced to a problem) in MAX SNP. Our methods introduce a general techique for creating approximation preserving reductions which show that any ``well'' approximable problem can be reduced (in an approximation preserving manner) to a problem which is hard to approximate to corresponding factors. We demonstrate this technique by applying it to the classes RMAX(2) and MIN$F^+\Pi_2$ which have the Set Cover problem and the Clique problem as complete problems, respectively. We use the syntactic nature of MAX SNP to define a general paradigm, {\em non-oblivious local search}, useful for developing simple yet efficient approximation algorithms. We show that such algorithms can find good approximations for all MAX SNP problems, yielding approximation ratios comparable to the best-known for a variety of specific MAX SNP-complete problems. Non-oblivious local search provably out-performs standard local search in both the degree of approximation