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

arXiv: https://arxiv.org/abs/2004.02437 · HTML: https://mlsanity.com/paper/2004.02437/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2020.

## Built on by (most cited first, 3 of 3)

- [Self-Supervision is All You Need for Solving Rubik's Cube](https://mlsanity.com/paper/2106.03157/) (2021)
- [Mechanistic Interpretability for Neural TSP Solvers](https://mlsanity.com/paper/2510.21693/) (2025)
- [Algorithm Design for Continual Learning in IoT Networks](https://mlsanity.com/paper/2412.16830/) (2024)

## Abstract (arXiv)

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.