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.