# The Approximation Ratio of the 2-Opt Heuristic for the Metric Traveling Salesman Problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

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

- [Bayesian Graph Traversal](https://mlsanity.com/paper/2503.05963/) (2025)

## Abstract (arXiv)

The 2-Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well-known Lin-Kernighan algorithm and often used in practice. So far, only upper and lower bounds on the approximation ratio of the 2-Opt heuristic for the metric TSP were known. We prove that for the metric TSP with n cities, the approximation ratio of the 2-Opt heuristic is √n/2 and that this bound is tight.