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

Standard

A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. / van Bevern, René ; Slugina, Viktoriia A.

In: Historia Mathematica, Vol. 53, 11.2020, p. 118-127.

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

BibTeX

@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.}",

note = "Rene van Bevern is supported by the Mathematical Center in Akademgorodok, agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation. Viktoriia A. Slugina is supported by grant No. 19-39-60006 of the Russian Foundation for Basic Research. Publisher Copyright: {\textcopyright} 2020 Elsevier Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

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.",

}

RIS

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.

N1 - Rene van Bevern is supported by the Mathematical Center in Akademgorodok, agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation. Viktoriia A. Slugina is supported by grant No. 19-39-60006 of the Russian Foundation for Basic Research. Publisher Copyright: © 2020 Elsevier Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

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

UR - https://elibrary.ru/item.asp?id=45515337

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 -

ID: 24395895