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 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 class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.
The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].
To separate FPT and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)nO(1), where f is a computable function and n is the size of the formula.
Contained in FPTnu, W[1], and FPR.
Contains FPTAS [CC97], as well as FPTsu.
Contains EPTAS unless FPT = W[1] [Baz95].
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].