Class Description

NPO: NP Optimization

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].

Contains APX and NPOPB.

Linked From

APX: Approximable

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].

More about...


FPTAS: Fully Polynomial-Time Approximation Scheme

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].

Contained in FPT [CC97].

More about...


GLO: Guaranteed Local Optima

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.

More about...


NLO: NL Optimization Problems

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 LNL.

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.

More about...


NPOPB: NPO Polynomially Bounded

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].

More about...


PTAS: Polynomial-Time Approximation Scheme

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].

More about...