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

René van Bevern; Viktoriia A. Slugina

doi:10.1016/j.hm.2020.04.003

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

René van Bevern, Viktoriia A. Slugina

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

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	https://doi.org/10.1016/j.hm.2020.04.003
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

Access to Document

10.1016/j.hm.2020.04.003

Cite this

@article{e08dd77cb2b0459eb6e377b5ba767b7b,

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

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 = "Christofides algorithm, Combinatorial optimization, Novosibirsk Akademgorodok, USSR",

author = "{van Bevern}, Ren{\'e} and Slugina, {Viktoriia A.}",

year = "2020",

month = nov,

doi = "10.1016/j.hm.2020.04.003",

language = "English",

volume = "53",

pages = "118--127",

journal = "Historia Mathematica",

issn = "0315-0860",

publisher = "Academic Press Inc.",

}

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 -

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

Abstract

Keywords

OECD FOS+WOS

Access to Document

Other files and links

Fingerprint

Cite this