Optimization, approximation, and complexity classes (Q1186548): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:38, 5 March 2024
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
MAX NP
0 references
MAX SNP
0 references
optimization
0 references
approximability
0 references