networks
How much can the railway carry?
It is 1955, and the Air Force's analysts are staring at a map of the Soviet rail network with a question that is really two questions: how much freight per day can flow from the Urals to Eastern Europe, and — the classified twin — which few links, if cut, would choke it. Formalize flow on a capacitated network, compute the maximum throughput, and prove the beautiful duality: the maximum flow exactly equals the capacity of the narrowest cut, so the interdiction question and the throughput question answer each other. The algorithm must terminate and scale to real maps. Get it wrong and logistics planning is guesswork — bridges bombed that reroute in a day, while the true bottleneck carries on untouched.
Who this problem belongs to
The two figures whose methods fit it best, out of 49 in contention.
Dantzig invented the simplex method in 1947 while working at the Pentagon and then RAND Corporation, the same institutional world this problem's 1955 Air Force rail-capacity analysis inhabits, and linear programming is the direct mathematical machinery for formalizing capacitated flow on a network and computing maximum throughput. His RAND colleagues in this exact period were the ones who first formalized the Soviet rail interdiction problem as a flow network, using LP duality to show that the max-flow value equals the min-cut capacity, precisely the duality this problem asks to be proved. Dantzig's simplex method could solve the resulting LP directly and was already known to terminate and scale to real transportation problems of the era's size. His score is not perfect only because the specialized combinatorial max-flow algorithms were refined by others shortly after.
Karp's polynomial-time max-flow algorithm, developed with Jack Edmonds in 1972 by proving shortest augmenting-path selection guarantees polynomial termination, is the direct technical descendant of exactly the problem this scenario poses: a capacitated network flow algorithm that provably terminates and scales to real maps. His broader career formalizing combinatorial optimization's complexity landscape gives him unmatched authority on what 'the algorithm must terminate and scale' actually requires as a mathematical guarantee rather than a hope. His Berkeley theory group also worked extensively on network flow and matching problems in the operations-research tradition this scenario belongs to. His score sits just below Dantzig's because Edmonds-Karp postdates the 1955 scenario by seventeen years, making his contribution the field's mature solution rather than its founding formalization.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
49 figures are scored on this problem. Draw it in a battle to see where you land.