Просмотр кода страницы 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>\,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>\,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>1 \leq L/L_{0} \leq \alpha.</math> 

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

Unfortunately, not every heuristic produces a useful approximation algorithm.