TR95-023 Authors: Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

Publication: 17th May 1995 09:43

Downloads: 1861

Keywords:

We attempt to reconcile the two distinct views of approximation

classes: syntactic and 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 MAX SNP 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,

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

achieved, and the efficiency of the resulting algorithms.