Next: Completeness in approximation classes Up: Introduction Previous: Terminology for graph problems Index

###
Approximate algorithms and approximation classes

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.

Definition 2

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.

Definition 3

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

Definition 4

An NPO problem A belongs to the class APX if it is approximable within , for some constant .

Definition 5

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 .

Definition 6

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.

Definition 7

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:

It is also easy to see that these inclusions are strict if and only if .

Next: Completeness in approximation classes Up: Introduction Previous: Terminology for graph problems Index