TY - JOUR
T1 - A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
AU - van Bevern, René
AU - Slugina, Viktoriia A.
PY - 2020/11
Y1 - 2020/11
N2 - 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.
AB - 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.
KW - Christofides algorithm
KW - Combinatorial optimization
KW - Novosibirsk Akademgorodok
KW - USSR
UR - http://www.scopus.com/inward/record.url?scp=85085000537&partnerID=8YFLogxK
U2 - 10.1016/j.hm.2020.04.003
DO - 10.1016/j.hm.2020.04.003
M3 - Article
AN - SCOPUS:85085000537
VL - 53
SP - 118
EP - 127
JO - Historia Mathematica
JF - Historia Mathematica
SN - 0315-0860
ER -