It is well-known that if an NPO problem can be solved in polynomial time, then its corresponding decision problem can also be solved in polynomial time. As a consequence, if , then any NPO problem whose corresponding decision problem is NP-complete is not solvable in polynomial time. In these cases we sacrifice optimality and start looking for approximate solutions computable in polynomial time.
Let A be an NPO problem. Given an instance x and a feasible solution y of x, we define the performance ratio of y with respect to x as
The performance ratio is always a number greater than or equal to 1 and is as close to 1 as y is close to the optimum solution.
Let A be an NPO problem and let T be an algorithm that, for any instance x of A, returns a feasible solution T(x) of x. Given an arbitrary function , we say that T is an r(n)-approximate algorithm for A if, for any instance x, the performance ratio of the feasible solution T(x) with respect to x verifies the following inequality:
If an NPO problem admits an r(n)-approximate polynomial-time algorithm we say that it is approximable within r(n).
An NPO problem A belongs to the class APX if it is approximable within , for some constant .
Let A be an NPO problem. An algorithm T is said to be an approximation scheme for A if, for any instance x of A and for any rational , returns a feasible solution of x whose performance ratio is at most .
An NPO problem A belongs to the class PTAS if it admits a polynomial-time approximation scheme, that is, an approximation scheme whose time complexity is bounded by q(|x|) where q is a polynomial.
Observe that the time complexity of an approximation scheme in the above definition may be of the type or where p is a polynomial. Thus, computations with values very close to 1 may turn out to be practically unfeasible. This leads us to the following definition.
An NPO problem A belongs to the class FPTAS if it admits a fully polynomial-time approximation scheme, that is, an approximation scheme whose time complexity is bounded by where q is a polynomial.
Clearly, the following inclusions hold: