Opening Max-st-Flow is a Linear Program
Max-st-Flow is a Linear Program
- Length
- 15 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
The maximum s-t flow problem becomes a linear program in this short graduate session of CMU 15-750, A Theorist's Toolkit, taught by O'Donnell. He opens with Dantzig's simplex talk, where Hotelling doubted the linearity assumption and von Neumann defended it. A directed graph with edge capacities, a source and a sink then carries one non-negative flow variable per directed edge. Capacity bounds and conservation at intermediate vertices become linear constraints, and the flow out of the source is the objective. The history runs from Tolstoy's 1930 work through Harris at RAND and Ford and Fulkerson to Khachiyan's 1979 polynomial-time result. Basic linear programming and graph terminology are assumed.

Your comment is kept while you sign up.Sign in
Writes max s-t flow as a linear program from edge variables, capacity bounds and conservation constraints.
The maximum s-t flow problem becomes a linear program in this short graduate session of CMU 15-750, A Theorist's Toolkit, taught by O'Donnell. He opens with Dantzig's simplex talk, where Hotelling doubted the linearity assumption and von Neumann defended it. A directed graph with edge capacities, a source and a sink then carries one non-negative flow variable per directed edge. Capacity bounds and conservation at intermediate vertices become linear constraints, and the flow out of the source is the objective. The history runs from Tolstoy's 1930 work through Harris at RAND and Ford and Fulkerson to Khachiyan's 1979 polynomial-time result. Basic linear programming and graph terminology are assumed.
This lecture
Lecture 56 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.