Viktoriia A. Slugina
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Viktoriia A. Slugina has a total of 1 co-authors. Here are the top co-authors by number of shared publications:
- René van Bevern
Department of Mechanics and Mathematics, Novosibirsk State University, Novosibirsk, Russian Federation
1 shared publication
Latest Publications
- Open Access
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.
Open AccessA 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.