ON SYNTACTIC VERSUS COMPUTATIONAL VIEWS OF APPROXIMABILITY

We attempt to reconcile the two distinct views of approximation classe s: syntactic and computational. Syntactic classes such as MAX SNP perm it structural results and have natural complete problems, while comput ational classes such as APX allow us to work with classes of problems whose approximability is well understood. Our results provide a syntac tic characterization of computational classes and give a computational framework for syntactic classes. We compare the syntactically defined class MAX SNP with the computationally defined class APX and show tha t every problem in APX can be ''placed'' (i.e., has approximation-pres erving reduction to a problem) in MAX SNP. Our methods introduce a sim ple, yet general, technique for creating approximation-preserving redu ctions which shows that any ''well''-approximable problem can be reduc ed in an approximation-preserving manner to a problem which is hard to approximate to corresponding factors. The reduction then follows easi ly from the recent nonapproximability results for MAX SNP-hard problem s. We demonstrate the generality of this technique by applying it to o ther classes such as MAX SNP-RMAX(2) and MIN F+ Pi(2)(1) which have th e clique problem and the set cover problem, respectively, as complete problems. The syntactic nature of MAX SNP was used by Papadimitriou an d Yannakakis [J. Comput. System Sci., 43 (1991), pp. 425-440] to provi de approximation algorithms for every problem in the class. We provide an alternate approach to demonstrating this result using the syntacti c nature of MAX SNP. We develop a general paradigm, nonoblivious local search, useful for developing simple yet efficient approximation algo rithms. 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-hard problems. Nonoblivio us local search provably outperforms standard local search in both the degree of approximation achieved and the efficiency of the resulting algorithms.