The course contents are divided into five broad themes.
- Network Flows and Bipartite Matchings: Recap of Ford Fulkerson method and max-flow min-cut theorem. Dinitz Algorithm, and Preflow push algorithm for max-flow. Reduction from flows to bipartite matchings. Application of max-flow min-cut theorem for structural and algorithmic results.
- Non-Bipartite matchings: Edmonds Maximum Matching Algorithm, Gallai Edmonds Decomposition theorem and applications, Tutte-Berge Formula.
- Linear Programming based algorithms: Introduction to Linear Programs, formulating combinatorial problems as Linear Programs, Notion of Dual, Primal Dual technique for exact and approximate algorithms -- weighted matchings, shortest paths.
- Matching Markets: Matchings with preferences, Stable matchings, House Allocation problem, notions of optimality and algorithms and hardness
- Recent topics: Recent developments related to the above topics will be discussed. Some candidate topics are dynamic graph algorithms, online algorithms, approximation algorithms related to the topics discussed above.