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 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 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].
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.
The class of optimization problems which can be solved in nondeterministic logspace.
Defined in [TAN07] as the logspace equivalent of NPO, where it is shown that the various logspace approximation classes form a hierarchy iff L ≠ NL.
As with the definition of NPO in [ACG+99], NLO is defined as a class of "structured" problems, comprising both a "solution relation" (indicating which solutions are acceptable for a given input) and a "measure function" (computing the value of each solution). The equivalent "unstructured" class is OptL. See [TAN07] for discussion.
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].
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].