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 it was published independently in the USSR in 1978. We provide some historic background on Serdyukovs findings and a translation of his article from Russian into English.
Download