A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. van Bevern, R. & Slugina, V. A. *Historia Mathematica*, 53:118-127, 2020. Preprint Poster Slides doi abstract bibtex 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 the same result was published independently in the USSR in 1978. We provide some historic background on Serdyukov's findings and a translation of his article.

@article{BS20b,
title = {A historical note on the 3/2-approximation algorithm
for the metric traveling salesman problem},
author = {René van Bevern and Viktoriia A. Slugina},
year = {2020},
date = {2020-11-17},
journal = {Historia Mathematica},
url_Preprint = {https://arxiv.org/abs/2004.02437},
url_Poster =
{https://figshare.com/articles/poster/Parallel_Roads_to_the_Traveling_Salesman_3_2-Approximation/12728723},
url_Slides =
{https://www.researchgate.net/publication/348297719_Algoritm_Kristofidesa_ili_Kristofidesa-Serdukova_Istoria_otkrytia_i_publikacii},
volume = 53,
pages = {118-127},
doi = {10.1016/j.hm.2020.04.003},
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 the same result was published independently in
the USSR in 1978. We provide some historic
background on Serdyukov's findings and a translation
of his article.}
}

Downloads: 0

{"_id":"Y3ywbHv58jJqy43r5","bibbaseid":"vanbevern-slugina-ahistoricalnoteonthe32approximationalgorithmforthemetrictravelingsalesmanproblem-2020","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Slugina, V. A."],"bibdata":{"bibtype":"article","type":"article","title":"A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Viktoriia","A."],"propositions":[],"lastnames":["Slugina"],"suffixes":[]}],"year":"2020","date":"2020-11-17","journal":"Historia Mathematica","url_preprint":"https://arxiv.org/abs/2004.02437","url_poster":"https://figshare.com/articles/poster/Parallel_Roads_to_the_Traveling_Salesman_3_2-Approximation/12728723","url_slides":"https://www.researchgate.net/publication/348297719_Algoritm_Kristofidesa_ili_Kristofidesa-Serdukova_Istoria_otkrytia_i_publikacii","volume":"53","pages":"118-127","doi":"10.1016/j.hm.2020.04.003","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 the same result was published independently in the USSR in 1978. We provide some historic background on Serdyukov's findings and a translation of his article.","bibtex":"@article{BS20b,\n title =\t {A historical note on the 3/2-approximation algorithm\n for the metric traveling salesman problem},\n author =\t {René van Bevern and Viktoriia A. Slugina},\n year =\t {2020},\n date =\t {2020-11-17},\n journal =\t {Historia Mathematica},\n url_Preprint = {https://arxiv.org/abs/2004.02437},\n url_Poster =\n {https://figshare.com/articles/poster/Parallel_Roads_to_the_Traveling_Salesman_3_2-Approximation/12728723},\n url_Slides =\n {https://www.researchgate.net/publication/348297719_Algoritm_Kristofidesa_ili_Kristofidesa-Serdukova_Istoria_otkrytia_i_publikacii},\n volume =\t 53,\n pages =\t {118-127},\n doi =\t\t {10.1016/j.hm.2020.04.003},\n abstract =\t {One of the most fundamental results in combinatorial\n optimization is the polynomial-time\n 3/2-approximation algorithm for the metric traveling\n salesman problem. It was presented by Christofides\n in 1976 and is well known as \"the Christofides\n algorithm\". Recently, some authors started calling\n it \"Christofides-Serdyukov algorithm\", pointing out\n that the same result was published independently in\n the USSR in 1978. We provide some historic\n background on Serdyukov's findings and a translation\n of his article.}\n}\n\n\n\n","author_short":["van Bevern, R.","Slugina, V. A."],"key":"BS20b","id":"BS20b","bibbaseid":"vanbevern-slugina-ahistoricalnoteonthe32approximationalgorithmforthemetrictravelingsalesmanproblem-2020","role":"author","urls":{" preprint":"https://arxiv.org/abs/2004.02437"," poster":"https://figshare.com/articles/poster/Parallel_Roads_to_the_Traveling_Salesman_3_2-Approximation/12728723"," slides":"https://www.researchgate.net/publication/348297719_Algoritm_Kristofidesa_ili_Kristofidesa-Serdukova_Istoria_otkrytia_i_publikacii"},"metadata":{"authorlinks":{"van bevern, r":"https://bibbase.org/show?bib=http%3A%2F%2Frvb.su%2Frvb.bib&commas=true"}}},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.457Z","downloads":7,"keywords":[],"search_terms":["historical","note","approximation","algorithm","metric","traveling","salesman","problem","van bevern","slugina"],"title":"A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem","year":2020,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}