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.
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.
If an NPO problem admits an r(n) -approximate polynomial-time algorithm we say that it is approximable within r(n) .
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.
Clearly, the following inclusions hold:
It is also easy to see that these inclusions are strict if and only if
.
Viggo Kann