Slides

1. Introduction to Linear Programming from the perspective of Set Cover

2. Introduction to network flow, Ford-Fulkerson.

3. Decomposition of standard flow in to flow paths (path packing).

4. Review of flow augmenting algorithms, matching and vertex cover in bipartite graphs.

5. Push-Relabel max flow algorithm: preliminaries.

6. Push-Relabel max flow algorithm: generic description and analysis.

7. Push-Relabel max flow algorithm: implementation in $O(n^3)$

8. Max flow with lower bounds

9. Proof of Dilworth Theorem

10. Minimum cycle mean algorithm PPTX with narrations (zipped): Minimum cycle mean algorithm

11. Min cost flow: definitions, Klein's algorithm, Scaling algorithm

12. Global min-cut algorithms in undirected graphs

13. Edge coloring (Vizing)

14. Maximum matching algorithm in general graphs

15. Introduction to linear programming

16. Fourier Motzking elimination

17. Farkas Lemma and Strong Duality