| Date | Topic | Reading/Handouts | PSets | |
|---|---|---|---|---|
| Th Sept 8 | Introduction | matching example, spanning tree game | PS1 out | |
| Tu Sept 13 | Bipartite matching (cardinality) | lecture notes | ||
| Th Sept 15 | Assignment problem | lecture notes, section 4.4 in book | PS1 due, solns | |
| Tu Sept 20 | Non-bipartite matching (cardinality) | lecture notes, section 4.3 in book | ||
| Th Sept 22 | Linear programming, systems of linear inequalities | lecture notes, sections 0.1, 0.2 in book | PS2 out | |
| Tu Sept 27 | LP duality, polyhedra (faces, dim, ...) | lecture notes, sections 0.5 in book | ||
| Th Sept 29 | Polyhedral Combinatorics, descriptions of polyhedra | lecture notes | PS2 due, solns | |
| Tu Oct 4 | Total Unimodularity | section 3 of matching notes, section 0.8 of book | PS3 out | |
| Th Oct 6 | Matroids | sections 1.1, 1.4 of book | ||
| Tu Oct 11 | Columbus Day | |||
| Th Oct 13 | Matroids: Greedy algorithm, circuits, representation | sections 1.2, 1.3, 1.4 of book | PS3 due, solns | |
| Tu Oct 18 | Matroids: rank, matroid polytope | sections 1.5, 1.7 of book | PS4 out | |
| Th Oct 20 | Intersection of matroids: applications | section 3.1 in book | ||
| Tu Oct 25 | Minimum cost arborescences | lecture notes | ||
| Th Oct 27 | Intersection of matroids: cardinality algorithm | section 3.2 in book | PS4 due, solns | |
| Tu Nov 1 | Matroid union, packing bases | notes | ||
| Th Nov 3 | Review | |||
| Tu Nov 8 | -- | |||
| Th Nov 10 | Quiz | |||
| Tu Nov 15 | Maximum Flow problem | Chapter 5 | ||
| Th Nov 17 | Minimum Cut Problem | minimum cut notes | PS5 out | |
| Tu Nov 22 | Ellipsoid algorithm for LP | ellipsoid notes | ||
| Th Nov 24 | Thanksgiving | |||
| Tu Nov 29 | Ellipsoid algorithm in Comb Opt | ellipsoid notes | ||
| Th Dec 1 | Min T-odd cut, Matching Polytope | PS5 due, PS5 solns, PS6 out | ||
| Tu Dec 6 | Traveling Salesman Problem | Chapter 7 in Cook et al. | ||
| Th Dec 8 | Traveling Salesman Problem | Chapter 7 in Cook et al. | PS6 due | |
| Tu Dec 13 | Review |