Approximation algorithm

Материал из WikiGrapp
Перейти к:навигация, поиск

Approximation algorithmаппроксимирующий алгоритм.

For the travelling salesman problem, as indeed for any other intractable problem it is useful to have a polynomial time algorithm which will produce, within known bounds, an approximation to the required result. Such algorithms are called approximation algorithms. Let \,L be the value obtained (for example, this may be the length of a travelling salesman's circuit) by an approximation algorithm and let \,L_{0} be an exact value. We require a performance guarantee for the approximation algorithm which could, for a minimisation problem, be stated in the form:

1 \leq L/L_{0} \leq \alpha.

For a maximisation problem we invert the ratio \,L/L_{0}. Of course, we would like \,\alpha to be as close to one as possible.

Unfortunately, not every heuristic produces a useful approximation algorithm.