Slides

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

2. Matrix Form of Linear Programming, Covering & Packing, Examples (max flow, min-cut)

3. Introduction to network flow, Ford-Fulkerson.

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

5. Push-Relabel max flow algorithm: part 1.

6. Push-Relabel max flow algorithm: part 2.

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

8. Max flow with lower bounds

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

10. Minimum cycle mean algorithm

11. Global min-cut algorithms in undirected graphs

12. Edge coloring (Vizing)

13. Maximum matching algorithm in general graphs

14. Introduction to linear programming

15. Fourier Motzking elimination

16. Farkas Lemma and Strong Duality

17. Duality and complementary slackness

18. Dual opt to primal opt (Simplex in a nutshell) and Arbitrage

19. Online routing