Optimization, approximation, and complexity classes (Q1186548)

The authors introduce a complexity class, called MAX NP, which is a variant of NP. They define also MAX SNP which is a subclass of MAX NP. These are classes of optimization problems that contain many known and well-studied problems. The main result of the paper is the proof that problems in these classes can be approximated with some bounded error. Additionally, the authors show that a number of common optimization problems are complete for MAX SNP under a specific transformation, \textit{L-reduction}, that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme if and only if the whole class does.