Approximation algorithm

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 [math]\displaystyle{ L }[/math] be the value obtained (for example, this may be the length of a travelling salesman's circuit) by an approximation algorithm and let [math]\displaystyle{ L_{0} }[/math] be an exact value. We require a performance guarantee for the approximation algorithm which could, for a minimisation problem, be stated in the form:

[math]\displaystyle{ 1 \leq L/L_{0} \leq \alpha. }[/math]

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

Unfortunately, not every heuristic produces a useful approximation algorithm.