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 NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.
Defined in [AP95], where it was also shown that GLO is strictly contained in APX.
[KMS+99] showed that MaxSNP is not contained in GLO.
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 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 class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."
Defined in [ACG+99].
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].