And once we have the definition of performance ration we can introduce the notion of approximation algorithm, that is an algorithm that, for any instance x, returns a solution whose performance ratio is at most r.
| First we need
to introduce the notion of performance ratio as a measure of quality of
solution y with respect to instance x performance ratio always
greater than 1: as closer it is to 1, as better is the quality of y. And once we have the definition of performance ration we can introduce the notion of approximation algorithm, that is an algorithm that, for any instance x, returns a solution whose performance ratio is at most r. |
|
