A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Preprint
Abstract
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 Serdyukov's findings and a translation of his article from Russian into English.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- On approximate data reduction for the Rural Postman Problem: Theory and experimentsNetworks, 2020
- Metric TSP2016
- Parameterized Algorithms2015
- Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphsCombinatorica, 2014
- Overview of New Approaches for Approximating TSP2013
- Traveling Salesman Problem2008
- Experimental Analysis of Heuristics for the STSP2007
- The Maximum TSP2007
- Heuristic analysis, linear programming and branch and bound1980
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973