Applications of LP Duality: Matchings, Flows and Shortest Path
In this video we put duality to use. Specifically, we will
1.) prove Hall's theorem, which characterizes when a bipartite graph has a perfect matching based on the duality of max-matching and min-vertex-cover in bipartite graphs (König's theorem)
2.) see two LP formulations of the Max-Flow, which lead to different formulations of Min-Cut (and proving through LP duality the Max-Flow Min-Cut theorem)
3.) Dualize the flow-based formulation of the shortest path problem
One tool used in these applications and discussed in the video are totally unimodular matrices.
00:00 Matchings
03:12 Hall's theorem
04:44 König's theorem
05:47 proof of Hall's theorem
10:00 totally unimodular matrices
12:46 LPs with totally unimodular matrix A
17:24 incidence matrices of bipartite graphs
21:01 König's theorem
26:27 Deriving the Max-Flow LP
30:20 The Max-Flow LP
31:44 Discussion of Max-Flow LP
34:08 Dualizing the Max-Flow LP
35:40 The Dual LP
37:46 Compacter formulation of Dual LP
38.51 Why the Dual LP describes Min-Cut
40:21 Alternative Max-Flow LP (s-t-paths)
42:09 Dual of alternative LP
43:39 Shortest-Path LP
45:34 Dualizing the Shortest-Path LP
Watch video Applications of LP Duality: Matchings, Flows and Shortest Path online without registration, duration hours minute second in high quality. This video was added by user Algorithms Lab 03 January 2024, don't forget to share it with your friends and acquaintances, it has been viewed on our site 525 once and liked it 11 people.