A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
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.
\section{Introduction}
\noindent
One of the most fundamental problems
in combinatorial optimization
is the traveling salesman problem,
formalized as early as 1832
\citep[cf.][Chapter~1]{ABCC06}:
given $n$~cities
and their pairwise distances,
find a shortest tour{}
to visit each city exactly once
and return to the starting point.

Finding the \emph{shortest} tour{}
is a computationally intractable problem
even in the special case
where the distances between the cities
satisfy the triangle inequality \citep{GJ79}.
\citet{Chr76} 
presented an $O(n^3)$-time \emph{3/2\hyp approximation algorithm}
for this special case:
it yields a tour{}
that is at most 3/2 times longer
than the shortest one.
It %
is
a prime example for approximation algorithms
that entered
textbooks
and encyclopedias as
``the Christofides algorithm''
or ``the Christofides heuristic''
\citep{GJ79,Chr79,Gut09,WS11,Bla16}.

Quite some efforts have been made
trying to improve it
\citep[cf.\ the surveys of][]{Vyg12,Sve13}.
One line of research aims for improving its running time:
there are many faster heuristics,
which
cannot guarantee 3/2-approximate solutions \citep{JM07},
yet $(3/2+\varepsilon)$-approximate solutions for
any~$\varepsilon>0$
are computable
by a randomized algorithm
in $O(n^2\log^4n/\varepsilon^2)$~time \citep{CQ17}.
Another line of research aims for improving the approximation factor,
which was successful only in special cases:
in polynomial time,
one can compute 8/7-approximate solutions if the distances are in~$\{1,2\}$
\citep{BK06},
7/5-approximate solutions if
the distances are lengths of shortest paths
in an unweighted graph \citep{SV14},
and $(1+\varepsilon)$\hyp approximate solutions
for any fixed~$\varepsilon>0$
if the cities are points in fixed\hyp dimensional
Euclidean \citep{Aro98,Mit99} or
doubling spaces \citep[using a randomized algorithm]{BGK16},
or if the distances are lengths of shortest paths
in a graph excluding some fixed minor \citep{DHK11}.

For general distances satisfying the triangle inequality,
the 3/2 approximation factor of \citeauthor{Chr76}' algorithm
remains the state of the art.\footnote{Actually,
  \citet{Wol80} showed
  that the length of the computed tours
  is within a factor 3/2
  not only of the optimum,
  but
  of a lower bound
  given by the optimal solution to a relaxation
  of an integer linear programming model.}
Recently,
a small but growing group of authors started referring
to it
as ``the Christofides-Serdyukov algorithm''
\citep{BDW98,DT10,BBMV19,GW19,SZ19,Tar19,TV19},%
\footnote{We deliberately omit articles coauthored by
  Serdyukov's former colleagues from this list.}
claiming that it was independently obtained
in the USSR by \citet{Ser78}.

\looseness=-1
At the one hand,
this claim is plausible:
in the beginning of the 70s,
a~lot of research on computationally intractable
problems was carried out parallely in the  USSR,
leading to independent proofs of seminal results
like the Cook-Levin theorem
about the NP\hyp completeness
of the satisfiability problem for Boolean formulas
\citep{Tra84}.
Moreover,
the submission date
given in
the journal article of \citet{Ser78},
January 27th, 1976,
predates
the report of \citet{Chr76}, dated February, 1976.
On the other hand,
such claims should be treated with caution:
for example,
the wide\hyp spread claim
that Kuratovski's theorem
was earlier proved in the USSR
has little support \citep{KQS85}.

We give some historic background
on \citeauthor{Ser78}'s findings,
which indeed supports the claim
of his independent discovery of the 3/2\hyp approximation algorithm
and sheds some light on the timely coincidence
of the publications of \citeauthor{Chr76} and \citeauthor{Ser78}.
We also provide a translation of \citeauthor{Ser78}'s article
in the appendix.



\section{Anatoliy I.\ Serdyukov (1951--2001)}
\noindent
The following information
about Serdyukov
can be found in \citet{BGS07}, \citet{Dem17},%
\footnote{The birth year 1952 given in the book edited by \citet{Dem17}
  is incorrect.}
the archives
of the Department of Mechanics and Mathematics
of Novosibirsk State University,
and the
State Public Scientific Technological Library
of the Siberian Branch of the Russian Academy of Sciences.

Anatoliy Ivanovich Serdyukov was born
on October 29th, 1951,
in Prokopyevsk,
a city in Kemerovo region (Western Siberia), USSR.
He graduated from
Novosibirsk State University in 1973,
after which
he was employed
in the structures of the Siberian Branch
of the Lenin Academy of Agricultural Sciences,
then at the
Institute of Cytology and Genetics
of the Siberian Branch of the Academy of Sciences of the USSR
(SB AS USSR),
and finally
at the Institute of Mathematics of the SB AS USSR
(now named the Sobolev Institute of Mathematics,
Siberian Branch of the Russian Academy of Sciences),
where he was working
until his death on February 7th, 2001.

In 1980,
already working at the Institute of Mathematics,
he was awarded the academic degree
of candidate of physico\hyp mathematical sciences.
\citeauthor{Ser80}'s \citeyearpar{Ser80} thesis
is on the complexity of finding Hamiltonian and Eulerian cycles in graphs.
His best known results are
approximation algorithms
for finding \emph{longest}
traveling salesman tours \citep[surveyed by][]{BGS07}.

Taking into account his graduation year
and the submission date of \citeauthor{Ser78}'s \citeyearpar{Ser78}
article, January 27th, 1976,
\citeauthor{Ser78}
must have obtained his 3/2\hyp approximation algorithm
as a young graduate student in about 1975.


  
  
  



\section{Circulation of Christofides' result between 1976 and 1979}
\noindent
Authors usually refer to \citeauthor{Chr76}' \citeyear{Chr76}
technical report at Carnegie-Mellon University (CMU)
as the source of the 3/2\hyp approximation algorithm
for the metric traveling salesman problem,
which some authors
do not consider as published
\citep[cf.][who also claims that ``Christofides never published his algorithm'']{Bla16}.

\looseness=-1
Apparently,
\citeauthor{Chr76}' technical report was not known
to a wide audience up to 1978. %
For example,
\citet{Kar77} and \citet{RSL77}
refer to Christofides' abstract
in the proceedings
of a symposium held at CMU in April 1976.
The proceedings
were published only in December 1976 \citep{Tra76}.
\citet{FHK76}
refer to the same abstract,
whereas later,
in the journal version of their article,
\citet{FHK78} refer to the technical report.
\citeauthor{Chr76}' technical report could have been popularized
in 1977,
when its abstract
stating the 3/2-approximation
was indexed by the NASA abstract journal
Scientific and Technical Aerospace Reports
\citep{Chr77}.

Some authors of that time,
for example \citet{LR79},
refer to a journal article of Christofides
that is to appear in the journal \emph{Mathematical Programming}.
In a combinatorial optimization textbook,
\citet{Chr79}
describes his algorithm
without proving the approximation factor,
referring to an article in press in \emph{Mathematical Programming}
for the proof,
not mentioning his technical report.
Interestingly,
according to the archives of \emph{Mathematical Programming},
his article was not published.
The algorithm with complete proof details
was published to a wide audience not later
than in the seminal textbook of \citet{GJ79}.

Summarizing,
\citet{Ser78} submitted his journal article in January 1976,
which predates all traces of \citeauthor{Chr76}' publications on this topic.
Thus,
it is plausible that \citet{Ser78}
obtained the result independently.

\section{Serdyukov's work between 1974 and 1978}
\noindent
\looseness=-1
We give some historic background
on the findings of \citeauthor{Ser78}
to shed some light on the
timely coincidence of
the publications
of \citet{Chr76} and \citet{Ser78}.
To this end,
it is helpful to interpret the 3/2-approximation algorithm
for the traveling salesman problem as follows:
A first step
computes a minimum\hyp cost spanning tree
that connects all the cities.
A second step
computes a shortest tour{} in the input graph
that traverses the edges of the spanning tree.




The second step is solved
using an approach earlier developed for the closely
related Chinese postman problem
of computing a shortest tour{}
traversing \emph{all} edges of a graph:
\citet{Chr73} and \citet{Ser74},
but also \citet{EJ73}, actively
study the Chinese postman problem at that time.
They all reduce it
to
the problem of finding a minimum\hyp cost perfect matching
on the
complete edge\hyp weighted graph
on all odd\hyp degree vertices of the input graph.%
\footnote{Notably,
\cite{Ser74} explicitly introduces
the  problem
that forty years later
is intensively studied as the Eulerian extension problem
\citep{SBNW11,HJM12,SBNW12,DMNW13,GWY17,BFTxx}.}
Surprisingly,
while 
\citeauthor{Chr73}, \citeauthor{EJ73}
solve the matching problem
using the polynomial\hyp time algorithm of \citet{Edm65b},
\citeauthor{Ser74}
reduces it
to an exponential number of matching problems in bipartite graphs.%
\footnote{In contemporary terms of parameterized complexity theory
  \citep[cf.][]{CFK+15},
  \cite{Ser74} merely describes a fixed\hyp parameter algorithm
for the Chinese postman problem
parameterized by the number of odd\hyp degree vertices in the input graph.}
Apparently,
in 1974
neither
\citeauthor{Ser74}
nor his reviewers
were aware
of the work of \citet{Chr73}, \citet{EJ73},
or
the
polynomial\hyp time
algorithm for computing maximum\hyp weight
matchings in general graphs,
published by \citeauthor{Edm65b} nine years earlier.

Since \citet{Ser78} uses \citeauthor{Edm65b}' algorithm
to solve the matching problem
in his 3/2\hyp approximation algorithm
for the traveling salesman problem
but was unaware of it in 1974,
he must have learned about \citeauthor{Edm65b}' algorithm
in 1974 or 1975.
One scenario is
that he learned about it
via the article of \citet{Chr73},
which \citet{Ser76} cites
in an article studying
reductions between matching, covering,
the Chinese postman, and the traveling salesman problems.
In this scenario,
\citeauthor{Ser78} obtained
his 3/2\hyp approximation
independently of \citeauthor{Chr73}
but because of him.
Another scenario is that
\citet{Ser78} learned about \citeauthor{Edm65b}' algorithm
from \citet{Kar76},
whose $O(n^3\log n)$\hyp time implementation
of \citeauthor{Edm65b}' algorithm
he uses in his 3/2\hyp approximation.
\citeauthor{Kar76}'s
article was probably not yet published in January 1976,
when \citeauthor{Ser78} submitted his article,
but he might have had access to a preliminary copy,
which is supported by the fact
that the titles given by \citeauthor{Ser78} and \citeauthor{Kar76}
differ slightly.

\section{Conclusion}
\noindent
Our findings support the claim that
\citet{Ser78} discovered the 3/2\hyp approximation algorithm
for the metric traveling salesman problem
independently of \citet{Chr76}.

Concerning the timely coincidence
of the publications of \citeauthor{Chr76} and \citeauthor{Ser78},
we conclude that,
on the one hand,
it was impossible for
\citeauthor{Ser78}
to find the algorithm
much earlier
than \citeauthor{Chr76},
being unaware of \citeauthor{Edm65b}'
polynomial-time matching algorithm
up to 1974.
On the other hand,
actively working on
the Chinese postman before,
he found the 3/2\hyp approximation
for the traveling salesman problem
as soon as he became aware of
\citeauthor{Edm65b}' algorithm.

\looseness=-1
An English abstract of \citeauthor{Ser78}'s \citeyearpar{Ser78}
article
was indexed in zbMATH only in 1982 \citep{Ser82}.
At~this time,
``the \citeauthor{Chr76} algorithm''
had already entered
fundamental textbooks like that of \citet{GJ79}.
Moreover,
the English abstract
does not mention any approximation factors.
Thus,
it is not surprising that \citeauthor{Ser78}'s result
remained largely unknown beyond the USSR.

\paragraph{Acknowledgments}
We thank Edward Kh.\ Gimadi and Oxana Yu.\ Tsidulko
for helpful input.

\paragraph{Funding}
René 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.


\bibliographystyle{tsp-history}

2020-04-28T02:07:16.000
2004
2004.02437
en
https://arxiv.org/abs/2004.02437
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.
Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); History and Overview (math.HO); Optimization and Control (math.OC)
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Qwen/Qwen-72B
1. YES
2. YES