Class Description

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

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


EPTAS: Efficient Polynomial-Time Approximation Scheme

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:

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


MaxNP: Maximization NP

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

More about...


MaxPB: MaxNP Polynomially Bounded

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

More about...


MaxSNP: Maximization SNP

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

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