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 languageEnglish
Pages (from-to)118-127
Number of pages10
JournalHistoria Mathematica
Volume53
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem'. Together they form a unique fingerprint.

Cite this