One idea, one story: secret min-cut

Ford and Fulkerson were introduced to the maximal flow through a network problem by Theodore E. Harris of the RAND corporation who, along with retired General F. S. Ross, had formulated a network model of railway traffic flow. The Harris-Ross work was classified secret as it dealt with the finding of a minimal cut of the railway network that shipped goods from the Soviet Union to Eastern Europe. Their work was declassified in 1999 based on a request by Alexander Schrijver (2002) to the Pentagon. Harris and Ross solved their problem by a heuristic "flooding" technique that greedily pushes as much flow as possible through the network. For their 44 node and 105 arc network, Harris and Ross determined a cut with capacity of 163,000 tons.

[On the history of the transportation and maximum flow problems, A. Schrijver, Mathematical Programming, B, 91, 3, 2002, 437-445]

[An Annotated Timeline of Operations Research : an informal history, Saul I. Gass, Arjang A. Assad, 2004]

Last modified: Thursday, 1 September 2016, 6:17 PM