## RenĂ© van Bevern and Viktoriia A. Slugina.
A historical note on the 3/2-approximation algorithm for the metric
traveling salesman problem.
*Historia Mathematica*, to appear.

One of the most fundamental results in combinatorial
optimization is the polynomial-time
3/2-approximation algorithm for the metric traveling
salesman problem. It was presented by Christofides
in 1976 and is well known as "the Christofides
algorithm". Recently, some authors started calling
it "Christofides-Serdyukov algorithm", pointing out
that the same result was published independently in
the USSR in 1978. We provide some historic
background on Serdyukov's findings and a translation
of his article.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.99.*