A Bit of History
The problem's earliest documented appearance is genuinely practical, not mathematical: an 1832 German handbook titled Der Handlungsreisende ("The Traveling Salesman"), written for actual traveling salesmen, casually described the value of planning an efficient round trip through a list of towns. Mathematicians formalized it a century later — Karl Menger (already met in Part 8 for his connectivity theorem) discussed it at a Vienna mathematical seminar around 1930, and Hassler Whitney (Part 11's Matrix-Tree contributor and Part 12's Dirac-theorem context) is credited with popularizing the "Traveling Salesman Problem" name in the mid-1930s. The watershed moment came in 1954, when George Dantzig, Delbert Ray Fulkerson (yes — the same Fulkerson of Ford-Fulkerson, an upcoming deep dive), and Selmer Johnson used linear programming to find and prove optimal a tour through 49 U.S. cities — a genuinely enormous computational achievement for the era, and the founding result of an entire subfield of operations research still active today.
TSP Fundamentals
Given a complete graph with edge weights (distances), find the minimum-weight Hamiltonian cycle (Part 12) — visit every vertex exactly once and return to the start, at minimum total cost. Variants matter: symmetric TSP assumes \(w(u,v) = w(v,u)\); asymmetric TSP does not (one-way streets, for instance); metric TSP assumes the triangle inequality holds (going directly is never longer than any detour) — a restriction that, as we'll see, makes good approximation possible.
NP-Hard, Building on Part 12's Warning
TSP is NP-hard (formally covered in Part 22) — it directly contains the Hamiltonian Cycle decision problem (itself NP-complete, from Part 12) as a special case: set every edge weight to 1, and "does a Hamiltonian cycle exist" becomes "is the optimal TSP tour exactly \(n\)?" No known algorithm solves TSP exactly in polynomial time for all inputs, and none is believed to exist.
Exact Approaches
Brute Force
Enumerate every permutation of vertices, compute each tour's total weight, keep the minimum. There are \((n-1)!/2\) distinct tours (fixing a start vertex and treating a tour and its reverse as identical) — perfectly correct, but explosively expensive: 20 cities already means more permutations than there are seconds since the Big Bang.
Held-Karp Dynamic Programming (Preview)
Michael Held and Richard Karp (the same Karp of Edmonds-Karp and Hopcroft-Karp, both upcoming deep dives) devised a dramatically better exact algorithm in 1962: dynamic programming over subsets of visited cities, defining \(\text{dp}[S][v]\) as the minimum cost to visit exactly the set \(S\) and end at vertex \(v\). This reduces the search from \(O(n!)\) to \(O(n^2 2^n)\) — still exponential, but a genuinely enormous practical improvement, solving instances with a few dozen cities that brute force could never touch. The full derivation, recurrence, and code live in an upcoming deep-dive batch.
Heuristics & Approximation
For instances too large even for Held-Karp, exact optimality is abandoned in favor of good, fast approximations:
- Nearest neighbor: repeatedly travel to the closest unvisited city. Simple and fast, but can produce arbitrarily bad tours in the worst case — a cautionary example of a greedy heuristic with no worst-case guarantee at all.
- 2-opt local search: starting from any tour, repeatedly find two edges whose removal-and-reconnection (swapping which pairs of cities are adjacent) shortens the tour, until no such improvement exists. Simple, surprisingly effective in practice, and the basis for many production TSP solvers' local-refinement step.
Christofides' Algorithm (Preview)
A 3/2-Approximation, Built from Parts Already in This Series
Nicos Christofides' 1976 algorithm guarantees a tour at most 1.5 times the optimal length for metric TSP — and remarkably, it's built entirely from tools already introduced: compute a minimum spanning tree (Part 11), find a minimum-weight perfect matching among the tree's odd-degree vertices (matching theory, Part 16), combine them into an Eulerian multigraph (Part 12), find an Eulerian circuit via Hierholzer's algorithm, then "shortcut" repeated vertices using the triangle inequality. Full derivation and code appear in an upcoming deep-dive batch.
Exercises
- Compute the number of distinct tours for \(n = 10\) cities using \((n-1)!/2\), and compare it to \(n^2 2^n\) from Held-Karp — at what \(n\) does Held-Karp's bound become the larger of the two?
- Run nearest-neighbor by hand on 5 cities arranged so that the greedy choice at the first step forces a very long final edge, demonstrating the heuristic's lack of a worst-case guarantee.
- Trace one 2-opt improvement step by hand on a small crossing tour (four cities where the naive tour's edges cross when drawn), showing how uncrossing the edges shortens the total distance.
- Challenge: Implement brute-force TSP for \(n \leq 10\) and Held-Karp's DP for the same instances, and verify they agree while measuring the dramatic runtime difference.
Conclusion & Next Steps
TSP is the canonical NP-hard optimization problem — brute force is correct but useless at scale, Held-Karp buys real headroom without sacrificing optimality, and Christofides' algorithm shows that earlier parts of this series (MSTs, Eulerian circuits, matching) combine into a genuinely strong approximation guarantee. Next, we turn to network flow — the machinery Christofides' matching step and much more besides ultimately depends on.
Next in the Series
In Part 15: Network Flow & Cuts, we meet the max-flow min-cut theorem and the algorithms that compute it — the backbone of bipartite matching, project selection, and more.