The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is a polynomial-time algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. (However, the exponent of the polynomial might depend strongly on ε.)
Contains FPTAS, and is contained in APX.
As an example, the Traveling Salesman Problem in the Euclidean plane is in PTAS [Aro96].
Defined in [ACG+99].
The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)
Contains PTAS.
Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].
Defined in [ACG+99].
The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.
Contains FPTAS and is contained in PTAS.
Defined in [CT97], where the following was also shown:
The subclass of NPO problems that admit an approximation scheme in the following sense. For any ε>0, there is an algorithm that is guaranteed to find a solution whose cost is within a 1+ε factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/ε.
Contained in PTAS.
Defined in [ACG+99].
Has the same relation to NP as MaxSNP does to SNP.
Contains MaxPB.
The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].
The subclass of MaxNP problems for which the cost function is guaranteed always to be bounded by a polynomial.
MinPB can be defined similarly.
Defined in [KT94].
The closure of MaxPB under PTAS reductions equals NPOPB [CKS+99].
The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP0. (Note: 'L' stands for linear -- this is not the same as an L reduction! For more details see [PY88].)
Defined in [PY88], where the following was also shown:
The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].
The subclass of NPO problems for which the cost function is guaranteed always to be bounded by a polynomial in n (the input size).
See [ACG+99].
NPOPB equals the closure of MaxPB under PTAS reductions [CKS+99].