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

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

8 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)118-127
Число страниц10
ЖурналHistoria Mathematica
Том53
DOI
СостояниеОпубликовано - ноя 2020

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА
  • 1.01.PO МАТЕМАТИКА, МЕЖДИСЦИПЛИНАРНЫЕ ПРИМЕНЕНИЯ
  • 6.01.MM ИСТОРИЯ
  • 6.01.MQ ИСТОРИЯ И ФИЛОСОФИЯ НАУКИ

Fingerprint

Подробные сведения о темах исследования «A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать