Travelling Salesman

Visit every city exactly once and return to the start, minimising total distance. NP-hard, and one of the most studied problems in computing.

Exact methods

Method	Time	Feasible $n$
Brute force over permutations	$O(n!)$	10-11
Held-Karp bitmask DP	$O(2^n{n}^2)$	20-22
Branch and bound with a 1-tree bound	exponential, good pruning	50-100
Cutting planes / Concorde	exponential	tens of thousands in practice

Held-Karp is the contest answer whenever $n\le 20$:

$\text{dp}[\text{mask}][i]={\min }_{j\in \text{mask}\setminus \{i\}}(\text{dp}[\text{mask}\setminus \{i\}][j]+w(j,i)).$

Approximation (metric TSP only)

The triangle inequality is required — without it, no constant-factor approximation exists unless P = NP.

Algorithm	Ratio	Time
Nearest neighbour	$\Theta (\log n)$	$O(n^2)$
Double the MST	2	$O(n^2)$
Christofides	$3/2$	$O(n^3)$
Karlin-Klein-Oveis Gharan (2020)	$3/2-10^{-36}$	polynomial
Euclidean PTAS (Arora)	$1+\epsilon$	$n(\log n{)}^{O(1/\epsilon )}$

Local search — what actually wins contests

For heuristic (“marathon”) problems, forget guarantees. Build a quick tour, then improve it:

2-opt. Pick two edges $(a,b)$ and $(c,d)$; replace them with $(a,c)$ and $(b,d)$, reversing the segment between. Accept if the total shrinks. The gain test is $O(1)$:

// tour[] is a permutation; try reversing tour[i..j]
long long delta = d(tour[i-1], tour[j]) + d(tour[i], tour[j+1])
                - d(tour[i-1], tour[i]) - d(tour[j], tour[j+1]);
if (delta < 0) reverse(tour.begin() + i, tour.begin() + j + 1);

Or-opt. Move a segment of 1-3 cities elsewhere without reversing.

Lin-Kernighan. Variable-depth $k$-opt. The strongest known local search; LKH implementations get within 1-2% of optimal on instances with millions of cities.

Wrap any of these in simulated annealing or random restarts to escape local minima. In practice 2-opt + Or-opt with a good neighbour list gets within 5% of optimal in seconds.

Variants

Variant	Notes
Path instead of cycle	drop the closing edge in Held-Karp
Asymmetric TSP ($w(i,j)\ne w(j,i)$)	Held-Karp unchanged; Christofides does not apply
Bitonic tour	$O(n^2)$ DP — a classic exercise; go left to right then right to left
Bottleneck TSP (minimise the largest edge)	binary search + Hamiltonian cycle existence
TSP with time windows	much harder; usually heuristic
Multiple salesmen (mTSP)	add $k-1$ copies of the depot
Vehicle routing (VRP)	TSP plus capacities; the industrial version
Steiner TSP	may skip non-required cities — see Dreyfus-Wagner

Lower bounds for pruning

Branch and bound lives or dies on its bound. The classic choices, in increasing strength:

1. Sum of the two cheapest edges at each city, halved.
2. MST of the unvisited cities plus the two cheapest connecting edges.
3. Held-Karp 1-tree bound — a Lagrangian relaxation that iteratively adjusts node penalties. Typically within 1% of optimal, and the reason Concorde can solve enormous instances exactly.

See also: Held-Karp · Christofides · Hamiltonian Path · Branch and Bound