Opening Min-st-Cut is the Dual LP of Max-st-Flow
Min-st-Cut is the Dual LP of Max-st-Flow
- Length
- 19 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Linear programming duality for optimization
Linear programming duality turns the max-st-flow problem into the min-st-cut problem, and O'Donnell derives the correspondence step by step. He starts from duality as a search for certifying multipliers that give upper bounds, with weak and strong duality. Taking the dual of the flow program yields a minimization over vertex potentials and edge variables . Simplifying that dual exposes the LP relaxation of min-st-cut, so strong duality equates maximum flow with minimum fractional cut, both computable in polynomial time. Lecture 18d of CMU's CS Theory Toolkit closes with the history through Ford, Fulkerson, Ted Harris and the Rand railway study.
Your comment is kept while you sign up.Sign in
Derives the dual linear program of max-st-flow to uncover the minimum st-cut problem and prove their equality.
Linear programming duality turns the max-st-flow problem into the min-st-cut problem, and O'Donnell derives the correspondence step by step. He starts from duality as a search for certifying multipliers that give upper bounds, with weak and strong duality. Taking the dual of the flow program yields a minimization over vertex potentials and edge variables . Simplifying that dual exposes the LP relaxation of min-st-cut, so strong duality equates maximum flow with minimum fractional cut, both computable in polynomial time. Lecture 18d of CMU's CS Theory Toolkit closes with the history through Ford, Fulkerson, Ted Harris and the Rand railway study.
This lecture
Lecture 59 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.