How do you pair things up without being greedy?
Network flow and min-cut (topic 06), its special case the transportation problem (18), which keeps only two flat layers of nodes, matching and assignment (07), and shortest paths with dynamic programming (08): the structure real shipping, scheduling and routing problems have.
Matching is the problem of pairing two sets (workers to shifts, donors to recipients, students to schools, taxis to riders) so that the whole arrangement is as good as possible. The trap is that the best arrangement is usually not made of the best individual choices. Somebody has to be given their second preference so that everybody else can be served, and no amount of local reasoning will find who.
The other reason matching matters here is that it is the direct ancestor of a modern idea. Edmonds' 1965 paper on matching is also where the modern definition of an "efficient algorithm" comes from: he argued that polynomial time was the right dividing line between practical and impractical. The complexity class P essentially starts in a paper about pairing people up.
And it runs inside a quantum computer. Decoding a surface code in real time (deciding which physical qubits to correct from the pattern of alarms) is solved as minimum-weight perfect matching. The algorithm keeping quantum error correction alive is an operations research result that predates the field it now serves by three decades.
The assignment problem as an integer program, with xij = 1 if worker i takes job j:
minimise Σᵢ Σⱼ cᵢⱼ xᵢⱼ
s.t. Σⱼ xᵢⱼ = 1 every worker gets exactly one job
Σᵢ xᵢⱼ = 1 every job gets exactly one worker
xᵢⱼ ∈ {0,1}
This looks like it should be NP-hard by topic 04's rule, and it is not, because the constraint matrix is totally unimodular. Relax xij ∈ {0,1} to 0 ≤ xij ≤ 1 and the LP's vertices are already integral (Birkhoff–von Neumann: the extreme points of the doubly-stochastic matrices are exactly the permutation matrices). So you may solve it as a linear program and the answer comes out binary by itself.
Algorithms: the Hungarian method (Kuhn, 1955; named for Kőnig and Egerváry, whose work it built on) runs in O(n³) in the form everyone now uses. Kuhn's own version was O(n⁴), and Munkres (1957) with later refinements brought it down. For general non-bipartite graphs, where odd cycles ruin the tidy structure, Edmonds' blossom algorithm (1965) still solves it in polynomial time by contracting odd cycles into single nodes. Surface-code decoding is the general case, which is why it is blossom and not Hungarian that runs there.
Kidney exchange A patient with a willing but incompatible donor can be matched into a chain: your donor gives to a stranger, whose donor gives to you. Finding the set of chains that saves the most lives is a matching problem on a graph of thousands of pairs, re-solved as the pool changes. It is non-bipartite (any pair can match any pair), it has side constraints real enough to hurt, and it is run for real by national programmes. This is the least abstract thing in this entire course.
And inside the machine Minimum-weight perfect matching is the standard decoder for the surface code. The alarms a quantum chip raises are matched to the likeliest set of underlying errors, in under a microsecond, continuously, or the computation dies.
Check yourself
Why does serving each worker their cheapest available job in turn fail to give the cheapest assignment?
In the example the greedy plan costs 10 and the true optimum is 9. The assignment problem is not NP-hard: its constraint matrix is totally unimodular, so it can be solved exactly in polynomial time.