Skip to content
PartialComputer Science·1930

Traveling Salesman Problem

Find the shortest closed route visiting every given city exactly once.

Formula

Optimization
min⁡π∈Sn∑i=1nd ⁣(vπi,vπi+1),πn+1=π1\min_{\pi\in S_n}\sum_{i=1}^{n}d\!\left(v_{\pi_i},v_{\pi_{i+1}}\right),\qquad \pi_{n+1}=\pi_1

Find the shortest Hamiltonian cycle visiting all n cities — the canonical NP-hard combinatorial optimization problem.

NP-hardness
TSP-Decision∈NP-complete\text{TSP-Decision}\in\mathbf{NP}\text{-complete}

Deciding whether a tour of cost ≤ k exists is NP-complete; no polynomial-time exact algorithm is known.

Christofides–Serdyukov bound
cost(TCS)≤32 OPT(metric TSP)\text{cost}(T_{\text{CS}})\le \tfrac{3}{2}\,\text{OPT}\quad\text{(metric TSP)}

The 1976 algorithm guarantees a tour within 3/2 of optimal for metric instances — unbeaten for nearly 50 years until Karlin et al. (2021).

Summary

The traveling salesman problem is a benchmark for optimization and computational complexity. Exact solutions are possible for many large instances, but the general problem is NP-hard and no polynomial-time exact algorithm is known.

Sources

Reducibility among combinatorial problems

1972

Solution of a large-scale traveling-salesman problem

1954

The Traveling Salesman Problem: A Computational Study

2006

Videos

Thumbnail for The Traveling Salesman Problem: When Good Enough Beats Perfect

The Traveling Salesman Problem: When Good Enough Beats Perfect

Reducible
Thumbnail for What is the Traveling Salesman Problem?

What is the Traveling Salesman Problem?

TED-Ed