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.
Original language | English |
---|---|
Pages (from-to) | 118-127 |
Number of pages | 10 |
Journal | Historia Mathematica |
Volume | 53 |
DOIs | |
Publication status | Published - Nov 2020 |
Keywords
- Christofides algorithm
- Combinatorial optimization
- Novosibirsk Akademgorodok
- USSR
OECD FOS+WOS
- 1.01 MATHEMATICS
- 1.01.PO MATHEMATICS, INTERDISCIPLINARY APPLICATIONS
- 6.01.MM HISTORY
- 6.01.MQ HISTORY & PHILOSOPHY OF SCIENCE