- Introduction to Linear Programming from the perspective of Set Cover
- Matrix Form of Linear Programming, Covering & Packing, Examples (max flow, min-cut)
- Introduction to network
flow, Ford-Fulkerson.
- Review of flow augmenting algorithms,
matching and vertex cover in bipartite graphs.
- Push-Relabel max flow algorithm: part
1.
- Push-Relabel max flow algorithm: part
2.
- Push-Relabel max flow algorithm:
implementation in
- Max flow with lower
bounds
- Min cost flow: definitions, Klein's
algorithm, Scaling algorithm
- Minimum cycle mean algorithm
- Global min-cut algorithms in undirected
graphs
- Edge coloring (Vizing)
- Maximum matching algorithm in general
graphs
- Introduction to linear programming
- Fourier Motzking elimination
- Farkas Lemma and Strong Duality
- Duality and complementary slackness
- Dual opt to primal opt (Simplex in a nutshell) and Arbitrage
- Online routing