Visit $n$ cities once each and return to the start, minimizing total distance. There are $(n-1)!/2$ feasible tours; at $n=20$ that is $6\times10^{16}$. But the real difficulty is not the count — it is that this space has no gradient. Every change replaces whole edges at once; you cannot "adjust the route slightly." Every intuition from continuous optimization about walking downhill is useless here.
Yet TSP is not formless. In the plane, an optimal tour never crosses itself: if two edges cross, reconnecting them is strictly shorter (triangle inequality). That is 2-opt — one geometric fact instantly deletes a huge slice of the search space. All the craft in combinatorial optimization consists of finding structure that deletes slices like that.
$\pi$ is one visiting order, $S_n$ is the set of all $n!$ permutations, $d$ is the distance between two cities, and the index wraps back to the start. The integer-programming form is more useful: $x_{ij}\in\{0,1\}$ says whether edge $(i,j)$ is used, each city gets one entry and one exit, plus subtour elimination constraints — without them the solution degenerates into several disconnected loops. There are exponentially many such constraints; Dantzig and colleagues in 1954 chose not to write them down, solving a relaxation and adding only the ones found violated. The cutting-plane method was born there.
TSP is simultaneously a specimen of two opposite things: it is the textbook NP-hard problem, yet the Concorde solver has exactly solved an 85,900-city instance with a certificate of optimality. No contradiction — NP-hardness is a statement about the worst case, while real instances carry geometric structure, and cutting planes convert that structure into constraints one at a time. The gap between "hard in theory" and "this instance is solvable" is where the entire operations-research industry stands.
Drill paths on circuit boards, laser cutting sequences, contig ordering in genome assembly, telescope observation scheduling, last-mile delivery — all are TSP or variants. On the heuristic side, LKH uses variable-depth edge exchanges and routinely lands within 1% of optimal on million-node instances.
If the optimum is out of reach, retreat one step: can you guarantee "my answer is never worse than 1.5× optimal," on every input? This differs from a heuristic in kind, not degree — a heuristic is "usually fine," an approximation algorithm is a promise with a proof.
The difficulty is a paradox: you do not know $\mathrm{OPT}$, so how can you prove you are near it? The way out is a computable lower bound. In TSP, deleting one edge from any tour leaves a spanning tree, so the minimum spanning tree is $\le \mathrm{OPT}$; it then suffices to prove "mine $\le c\times$ bound $\le c\times\mathrm{OPT}$." The whole field is, at bottom, the craft of constructing good lower bounds.
$\mathrm{ALG}(I)$ is what the algorithm returns on instance $I$, $\mathrm{OPT}(I)$ is the true optimum, and $\rho$ does not depend on the instance. Christofides' algorithm — a minimum spanning tree plus a minimum perfect matching on the odd-degree vertices — gives $\rho=3/2$ for TSP with the triangle inequality. That 1976 record stood until 2020, when it was nudged to $3/2-10^{-36}$: numerically negligible, but proof that $3/2$ is not a wall.
Approximation unfolds the binary P vs NP question into a continuous spectrum: not "can it be solved efficiently" but "how closely can it be approached efficiently." Better still, the spectrum has provable hard edges — the PCP theorem shows that unless P=NP, the $\ln n$ for set cover is already optimal and max clique resists even $n^{1-\varepsilon}$. "How hard" stops being a complaint and becomes a quantity you can compute.
Greedy $\ln n$ set cover is the skeleton of data subset selection and test-suite minimization; LP relaxation with randomized rounding is the standard recipe for cloud scheduling and budget allocation. The most direct link to machine learning: maximizing a submodular function under a matroid constraint carries a $1-1/e$ greedy guarantee (Nemhauser et al., 1978), used for sensor placement, dataset distillation, and few-shot exemplar selection — "pick a diverse, representative subset" almost always takes this form.
Tasks on one side, workers on the other, an edge meaning "can do it"; find the largest set of disjoint pairs. Greedy gets stuck: a pair taken early can block two pairs later.
The fix is the augmenting path: start from an unmatched vertex and alternate unmatched edge, matched edge, unmatched edge…; if you end at another unmatched vertex, flip every edge along the path — matched ones release, unmatched ones connect. The path holds one fewer matched edge than unmatched, so flipping raises the total by exactly $+1$. The elegance: it dismantles your earlier mistakes automatically, with no backtracking. Berge's theorem goes further — a matching is maximum $\iff$ no augmenting path exists. Global optimality compresses into a locally checkable condition.
On the left $M$ ranges over all matchings and $C$ over all vertex covers (vertex sets touching every edge): the maximum matching equals the minimum cover. That is duality — the answer to "how many pairs at most" is simultaneously the proof of "why not more." On the right $N(S)$ is the neighborhood of $S$: a perfect matching fails exactly when some subset has too few candidates. The bottleneck is always a specific subset, never some mystical global congestion.
In general graphs augmenting paths break down: an odd cycle lets the alternating walk fold back on itself. Edmonds' 1965 answer was the blossom — contract the entire odd cycle to a single vertex, keep searching in the contracted graph, expand afterward. In that same paper he first argued that a "good algorithm" should mean one whose running time grows polynomially. The definition of P, the central class of complexity theory, comes from a paper about how to pair things up.
The US kidney paired-exchange program (UNOS) saves lives with maximum-weight matching; residency assignment, real-time ad allocation (online bipartite matching's RANKING algorithm has competitive ratio $1-1/e$), and data association in object tracking all run the same machinery. And optimal transport is precisely the continuous relaxation of matching; Sinkhorn iteration makes it differentiable, which is why it now appears in diffusion models and domain adaptation.
Greedy — always take what looks best right now, never reconsider — is sometimes astonishingly right (Kruskal's minimum spanning tree) and sometimes catastrophically wrong (nearest-neighbor TSP). When exactly is greedy correct? Matroids answer this completely.
Start from a coincidence: "linearly independent sets of vectors" in linear algebra and "acyclic edge sets (forests)" in graph theory behave identically. First, subsets stay independent. Second, whenever two independent sets differ in size, some element of the larger can be added to the smaller while keeping it independent. Take those two as axioms and you have a matroid. The second is the crux: it guarantees that wherever you start, you never reach a dead end where the set is not yet maximum but nothing can be added.
A matroid is a pair $(E,\mathcal{I})$: $E$ is a finite ground set (all edges, all vectors) and $\mathcal{I}$ is a family of subsets called independent, containing the empty set, closed under taking subsets, and satisfying the exchange axiom above. An immediate consequence: all maximal independent sets have the same size, and that common size is the rank — the rank of a matrix in a vector space, the number of edges in a spanning forest in a graph.
The Rado–Edmonds theorem: greedy returns the optimum for every weight function if and only if the structure is a matroid. This is an exact "if and only if," not folklore about greedy usually working — mathematics rarely gets to fence off the applicability of an entire class of algorithms in one stroke. The line extends: the intersection of two matroids is still polynomially solvable (bipartite matching is exactly the intersection of two partition matroids), while three is NP-hard. The watershed sits between two and three.
Kruskal's algorithm is simply greedy on a graphic matroid; single-machine scheduling with deadlines and network reliability live in the same framework; linear codes in coding theory correspond to vector matroids. In machine learning, submodular functions generalize matroid rank functions: data subset selection, active learning, recommendation diversity, and in-context exemplar choice are nearly all "maximize a submodular function under a matroid constraint" — the $1-1/e$ from Concept 2 grows out of exactly this structure.