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

[raghavbalaji]

long time no see. please continue posting. this is a great channel where i have learnt so much about various domains of math and CS. your explanations are super neat. hoping for your comeback

[FlashTheMusik]

Thanks for the video! I was wondering for the Min cut - Max Flow LP why the Cut that was displayed in 40:21 did not look minimal to me. The edges that are cut (in the original graph in 29:47) have a summed up cost of 12 whereas cutting away the vertices so the new connected components are {o, a} and {b, c, d, e, n} would have a min cut cost of 4 which is equal to the max flow of the network. Did I miss something in the example?

[mayuinc]

Hey can you guys do a trajectory on an ideal pathway to learning computational geometry, beginning with high school algebra?