optimization
The assignment in the sky
It is the mid-twentieth century, and an airline (or an army) must match five hundred pilots to five hundred routes, each pairing carrying a different cost, to minimize the total — and the number of possible assignments is a factorial so vast that trying them all would outlast the universe. Yet the problem has hidden combinatorial structure that makes an exact, fast solution possible. Find it: exploit that structure to solve the assignment provably optimally and quickly, rather than settling for a greedy guess. Get it wrong and you brute-force a problem brute force cannot touch, or accept a suboptimal matching that wastes fuel, crews, and money daily at scale — combinatorial structure, once seen, turns an impossible search into an easy one.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
Dantzig is nearly the author of this problem. He created the simplex method in 1947, and the assignment problem was among the first he attacked with it; his Air Force work in project SCOOP concerned precisely military deployment and scheduling at pilots-to-routes scale. He showed how the transportation and assignment problems yield to linear programming with specialized network simplex variants, and the tightness of the LP relaxation over the Birkhoff polytope was clarified in exactly his orbit, with von Neumann and with Kuhn's 1955 Hungarian method, which Dantzig knew and taught. On mid-century hardware his methods actually solved such instances for airlines and armies; that is documented history, not speculation. He would formulate it as a min-cost network problem, exploit total unimodularity for integrality, and deliver the provable optimum with a dual certificate. This is his home turf, full stop.
Karp is a founder of exactly this subject. With Edmonds he gave the polynomial max-flow analysis (Edmonds-Karp, 1972) whose scaling ideas power min-cost-flow assignment solvers; with Hopcroft he gave the O(E sqrt V) bipartite matching algorithm (1973) that is still the standard; and his 1972 reducibility paper drew the map on which matching sits famously inside P while its neighbors go NP-complete, the very boundary this problem dramatizes. Later work on parallel matching (with Upfal and Wigderson) and probabilistic analysis of combinatorial algorithms extends the same program. Asked to match 500 pilots to 500 routes, he would formulate it as min-cost bipartite matching, deploy a primal-dual or scaling algorithm with a complexity bound he personally helped establish, and certify optimality by duality. Only Dantzig's operational LP priority rivals him; the modern algorithmic answer is substantially Karp's own.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.