| Date | Topic | Reference | |
|---|---|---|---|
| Aug 1 | Introduction + Administrative announcements | None | |
| Aug 2 | Network Flows and Cuts | CLRS Section 26.1 | |
| Aug 6 | Image Segmentation: An application | Kleinberg and Tardos Section 7.10 | |
| Aug 7 | Review of Ford Fulkerson Method | CLRS Section 26.1, 26.2 | |
| Aug 8 | Proof of Max-Flow Min-cut theorem and Push Relabel Algorithm | CLRS Section 26.2, 26.4 | |
| Aug 9 | Push Relabel Algorithm (invariants) | CLRS Section 26.4 | |
| Aug 13 | Push Relabel Algorithm (analysis) | Roughgarden's notes on Push-Relabel | |
| Aug 14 | Bipartite Matchings and Flows (reduction) | CLRS Section 26.3 | |
| Aug 20 | Proof of Halls Theorem via max-flow min-cut theorem | Kleinberg and Tardos Section 7.3 | |
| Aug 21 | Dulmage Mendelsohn Decomposition | Notes (Proof in class was via network flows) | |
| Aug 22 | Hopcroft Karp Algorithm | Graph Theory book by DB West. | |
| Aug 23 | Hopcroft Karp Algorithm (continued) | Notes by Sameer Khuller | |
| Aug 27 | Matchings without short augmenting paths. Non-bipartite matchings Tutte Berge formula. |
||
| Aug 28 | Why does layered network not work for non-bipartite graphs? Need to define blossoms. Defintion of a blossom and examples. |
||
| Aug 29 | Correctness of blossom shrinking. | ||
| Aug 30 | Quiz 1 | ||
| Sept 3 | Discussion of Quiz 1 answers and grading policy. |
||
| Sept 4 | An implementation of Edmonds algorithm using union-find. |
See Notes by Uri Zwick | |
| Sept 5-6 | Gallai Edmonds Decomposition Theorem. |
Notes coming up!! | |
| Sept 9 | A Detour: TSP, inapproximability, Metric TSP, 2-approx and 3/2-approx. algo. |
See Roughgarden's Notes on TSP (Section 1 and Section 2) | |
| Sept 12 | Introduction to LPs, Example, Duality. |
Class Notes by TA. For additional reading, see Chapter 7 of DPV book on Algorithms. | |
| Sept 13 | Forumulating LP for matching, vertex cover. |
Class Notes by TA. | |
| Sept 17 | Maximum Weight Perfect Matching. |
Class Notes by TA. | |
| Sept 18 | Primal-Dual Algorithm for Weighted Bipartite Matching. |
Class Notes by TA. | |
| Sept 19 | Primal Dual Algorithm for Shortest Path. |
Class Notes by TA. | |
| Sept 20 | Primal Dual Algorithm for Shortest Path (continued). |
Approximation Algorithms by Shmoys and Williamsons (Section 7.3) | |
| Sept 24 | Weighted Vertex Cover. |
Class Notes by TA. | |
| Sept 24 | Weighted Vertex Cover. |
Class Notes by TA. | |
| Sept 25 | Complementary Slackness (derivation) and a general scheme for approximation algorithms. |
Class Notes by TA. | |
| Sept 26 | Steiner Tree Problem and a simple 2-approximation. |
Class Notes by TA. | |
| Sept 26 | Generalized Steiner Tree Problem. |
Shmoys and Williamsons. Section 7.4 | |
| Sept 27 | Generalized Steiner Tree Problem (continued). |
Shmoys and Williamsons. Section 7.4 | |
| Oct 3 | LP for Max-flow and its Dual. Interpretation of Dual. |
Class Notes by TA. | |
| Oct 4 | Min-Cost Max Flow. Relation with other problems. Successive Shortest path algo. |
Class Notes by TA. | |
| Oct 9 | Min-Cost Max Flow. Primal Dual and Complementary Slackness conditions. |
Class Notes by TA. | |
| Oct 10 | Min-Cost Max Flow continued. |
Class Notes by TA. | |
| Oct 11 | Min-Cost Max Flow continued. |
Class Notes by TA. | |
| Oct 15 | Class cancelled (Prof. Karp's visit) | ||
| Oct 16 | Introduction to stable matchings. | Notes emailed to class. | |
| Oct 17 | Properties of the stable matching. | Class Notes by TA. | |
| Oct 17 | Variants of the stable matching problem. | Class Notes by TA. | |
| Oct 22 | Student Presentation (Flow algorithms for planar graphs) | ||
| Oct 23 | Maximum cardinality weakly stable matchings |
Kiraly's paper (2/3 approx. for ties on one side) | |
| Oct 24 | Maximum cardinality popular matchings |
Kavitha's paper. | |
| Oct 25 | Maximum cardinality popular matchings continued |
Kavitha's paper. | |
| Oct 29 | Student Presentation (Flow Games) | ||
| Oct 30 | An application of stable matching: Dinitz Problem. | Chapter 33, Proofs from the book. | |
| Oct 31 | An application of stable matching: Dinitz Problem -- continued. | Chapter 33, Proofs from the book. | |
| Nov 1 | List coloring of Planar Graphs. | Chapter 34, Proofs from the book. | |
| Nov 5--6 | Edge Coloring and a additive one approximation algorithm. | Chapter 7, DB West, Introduction to Graph Theory. |