A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem

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.

arXiv commentVersion accepted to Historia Mathematica

References in corpus (2)

• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• On approximate data reduction for the Rural Postman Problem: Theory and experiments

Cited by in corpus (5)

• How many quantum gates do gauge theories require?
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
• SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition