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 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.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Worst-Case Analysis of a New Heuristic for the Travelling Salesman ProblemOperations Research Forum, 2022
- Rural postman parameterized by the number of components of required edgesJournal of Computer and System Sciences, 2017
- Metric TSP2016
- On Eulerian extensions and their application to no-wait flowshop schedulingJournal of Scheduling, 2011
- From Few Components to an Eulerian Graph by Adding ArcsLecture Notes in Computer Science, 2011
- Traveling Salesman Problem2008
- The Maximum TSP2007
- The theorem on planar graphsHistoria Mathematica, 1985
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973
- The optimum traversal of a graphOmega, 1973