| Date | Topic | Reference | Slides | Link |
|---|---|---|---|---|
| Jan 17 | Introduction + Administrative announcements | None | Slides | Link |
| Jan 18 | Max-Flow Problem, definition of flow, value of flow. | CLRS Ch. 26.1 | Slides | Link |
| Jan 19 | Residual Network, augmenting the flow, Ford Fulkerson method. | CLRS Ch. 26.2 | Link | |
| Jan 21 | Flows and Cuts, Capacity and Netflow across a cut. Relation to max-flow value, max-flow min-cut Theorem. | CLRS Ch. 26.2 | Slides | Link |
| Jan 24 | Proof of max-flow min-cut theorem, Different ways to obtain min-cut, what if min-cut is unique? | CLRS Ch. 26.2 | Link | |
| Jan 25 | Edmonds Karp algorithm, using shortest paths and a strongly polynomial time algorithm | CLRS Ch. 26.2 | Link | |
| Jan 28 | Matchings, maximal and maximum, alternating and augmenting paths, proof of Berge's theorem | Link | ||
| Jan 31 | Bipartite matchings and Flows, Vertex Covers and Matchings, Konigs theorem and proof via network flows | Slides | Link | |
| Feb 1 | Proof of Konigs theorem, Properties invariant of a maximum matching | Link | ||
| Feb 2 | Dulmage Mendelsohn Decomposition Theorem statement and examples | Link | ||
| Feb 4 | Dulmage Mendelsohn Decomposition Theorem proof via max-flow min-cut | Link | ||
| Feb 7 | Push Relabel Algorithm for computing max-flow | CLRS (Sec. 26.4) Kleinberg and Tardos (Sec. 7.4) | Link | |
| Feb 8 | Push Relabel Algorithm for computing max-flow continued | Lecture Notes by Prof. Roughgarden | Link | |
| Feb 9 | Bounding Number of Relabel and Push operation | Slides | Link | |
| Feb 11 | Variants of Bipartite Matching and Max Flow problem: Reductions. | Slides | Link | |
| Feb 14 | Matchings in General Graphs: Edmonds Algorithm | Slides | Link | |
| Feb 15 | Edmonds Algorithm: Blossom Shrinking | Link | ||
| Feb 16 | Edmonds Algorithm: description, running time | Link | ||
| Feb 18 | Tutte's Theorem Statement, Implications, Setup for GE decomposition Theorem | Slides | Link | |
| Feb 21 | Gallai Edmonds decomposition Theorem and its proof. | Link | ||
| Feb 22 | Gallai Edmonds decomposition Theorem and its proof. | Link | ||
| Feb 23 | Tutte's Theorem (proof). | Slides | Link | |
| Feb 28 | Introduction to Linear Programs, Formulating graph problems as LPs. | Slides | Link | |
| Mar 1 | LPs and Hitting Set problem. Vertex Cover, MST, Shortest paths using Hitting set | Link | ||
| Mar 2 | Linear Programs and Duals. | Link | ||
| Mar 4 | More examples of Duals. | |||
| Mar 7 | MidSem Discussion. | Slides | ||
| Mar 8 | Weak Duality and Primal Dual Algo for Hitting Set | Link | ||
| Mar 9 | 2-approx for vertex cover using Hitting Set. Shortest Path Primal Dual Algorithm. | Slides | Link | |
| Mar 11 | Shortest Path Analysis. Maximum weight matching. | Slides | Link | |
| Mar 14 | Maximum weight matching in bipartite graphs. | Link | ||
| Mar 15 | Perfect Matching polytope for Bipartite graphs | Slides | Link | |
| Mar 16 | Half integrality of the general matching polytope | Slides | Link | |
| Mar 18 | No class: Holi. | |||
| Mar 21 | Short Quiz2 | |||
| Mar 22 | Matching markets : Introduction to Stable matchings | Link | ||
| Mar 23 | Stable matchings | Slides | Link | |
| Mar 25 | Stability vs. Popularity | Link | ||
| Mar 28 | Popular Matchings modified GS algorithm | Link | ||
| Mar 29 | Popular Matchings continued | Link | ||
| April 5 | Popular Matchings two-sided preferences (proof using LP duality) | Paper1 (Sec 2) Paper2 (Sec 3.1) proof of popularity using dual certificate | Slides | Link |
| April 6 | Two-sided preferences with ties (weakly stable matchings) | Paper (Sec 2) | Slides | Link |
| Mar 30 | Popular Matchings (one-sided preferences)[Lecture by Girija Limaye] | Slides | Link | |
| April 1 | Popular Matchings (one-sided preferences) continued[Lecture by Girija Limaye] | Slides | Link | |
| April 4 | Popular Matchings (one-sided preferences) continued | Paper | ||
| April 8 & 11 | Stable Roommates problem | Paper | Part1 Part2 |