Rene van Bevern, Head of the Algorithm Laboratory, NSU Department of Mechanics and Mathematics and Victoria Slugina, Deputy Director of Research at the Humanities Institute, studied the origin of the algorithm for a classic combinatorial optimization problem, “the traveling salesman”. In their article, the researchers argue that Anatoly Ivanovich Serdyukov, a Soviet scientist at the Novosibirsk Institute of Mathematics, constructed the world-famous “Christofides algorithm” independently and submitted it for publication earlier than Christofides. The NSU scientists published their findings on the “Historia Mathematica” website. This is the official journal for the International Commission on the History of Mathematics and the International Union of History and Philosophy of Science.
The traveling salesman problem was formulated in 1832 and consists of finding the shortest route for visiting “n” cities and returning to the original city. The problem belongs to the NP- hardness group of problems that have unknown solution algorithms. However, in February 1976 Nikos Cristofides proposed an algorithm that effectively constructs a route whose length does not exceed 3/2 of the optimum for the metric case when the distances between cities satisfy triangle inequality. This is one of the first approximate algorithms for the NP-hardness problem, and so far, no algorithm with a better guarantee of accuracy is known for the metric case.
van Bevern talked about the origin of this research,
When I arrived in Novosibirsk, colleagues at the Institute of Mathematics referred to what is called the “Christofides algorithm” in all textbooks as the “Christofides-Serdyukov algorithm”. I was working in the Institute of Mathematics at the time and in the office, there was a copy of the 1978 issue of the “Controlled Systems” journal with the corresponding article by Serdyukov. I was surprised that Christofides exact algorithm was proposed there. The article indicates the date the article arrived in the editorial office was January 1976 that is a month ahead of Christofides publication. I wondered how such this was possible and why, outside the Institute of Mathematics, few people knew about Serdyukov’s result? Five years later, I turned to my friend and historian, Victoria Slugina, and we started the research. We found Serdyukov’s early works and looked for traces of the Christofides result.
The NSU scientist’s article reflects that the Christofides algorithm was proposed in February 1976 but that the technical report describing the algorithm was little known until 1978. The first complete description of the Christofides algorithm with proof of correctness was published in 1979 in the popular Garey and Johnson textbook, “Computers and Intractability: A Guide to the Theory of NP-Completeness”.
Serdyukov built the algorithm as a young graduate student at the Institute of Mathematics, Siberian Branch of the USSR Academy of Sciences. As early as 1973-1974, he and Christofides independently worked on the travel routing problem. However, according to the authors of the study, it is clear from Serdyukov’s work that he did not know the most important ingredient for his traveling salesman problem algorithm until 1974. This was the polynomial algorithm for finding the maximum matching in a graph that was published in the USA in 1965. In his article on the traveling salesman, Serdyukov uses this algorithm referring to a book published in the USSR in 1976. This explains the timing coincidence of results for Serdyukov and Cristofides. Serdyukov could not have obtained the result earlier without knowing the maximum matching algorithm.
Slugina noted,
On the one hand, the history of the origin of the one algorithm we examined shows the high level of expertise by the scientists in Akademgorodok and the relevance of research topics that were developed at the institutes of the Siberian Branch of the USSR Academy of Sciences. On the other hand, the lack of a universal international knowledge base at that time and the difficulty of academic mobility for Soviet specialists led to many of their results not being accessible to a wide circle of Western researchers. Conversely, the results of European and American authors were unknown or delayed in reaching Soviet scientists.
