论文标题
关于公制旅行者问题的3/2-鉴定算法的历史记录
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
论文作者
论文摘要
组合优化的最基本结果之一是公制旅行人员问题的多项式时间3/2- approximation算法。它是由Christofides在1976年提出的，被称为“ Christofides算法”。最近，一些作者开始称其为“ Christofides-Serdyukov算法”，指出它是在1978年独立出版的。我们提供了有关Serdyukov的发现以及他的文章从俄语翻译成英语的历史背景。
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.
