A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

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

Institution:	1. Department of Mechanics and Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation;2. Institute of History of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russian Federation;3. Humanities Institute, Novosibirsk State University, Novosibirsk, Russian Federation;1. Centro Interuniversitário de História das Ciências e da Tecnologia - Pólo Universidade de Lisboa, Faculdade de Ciências, Edif. C4, Piso 3, Gabinete 15, Campo Grande, 1749-016 Lisboa, Portugal;2. Escola Superior de Educação de Viseu, Rua Maximiano Aragão, 3504 - 501 Viseu, Portugal;1. Università degli Studi della Basilicata, Dipartimento di Matematica, Informatica ed Economia, Via dell''Ateneo Lucano, 10, 85100 Potenza, Italy;2. Università del Molise, Dipartimento di Bioscienze e Territorio, Contrada Fonte Lappone, Pesche, Isernia, Italy

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.

Keywords:	Combinatorial optimization Christofides algorithm USSR Novosibirsk Akademgorodok
本文献已被 ScienceDirect 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏