Optimization, approximation, and complexity classes (Q1186548)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Optimization, approximation, and complexity classes
scientific article

    Statements

    Optimization, approximation, and complexity classes (English)
    0 references
    28 June 1992
    0 references
    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.
    0 references
    0 references
    MAX NP
    0 references
    MAX SNP
    0 references
    optimization
    0 references
    approximability
    0 references
    0 references
    0 references