**When and where: **
The class meets virtually Tuesdays and Thursdays from 11AM to 12:30PM using Zoom (Kerberos authentication required) . Lectures are recorded, but attendance is strongly encouraged. Apart from lecture, don't forget to join the course ** Slack ** through canvas! Thanks to the creators of abot for giving us free access to their anonymous poll Slack app.

**Instructor:** Cole Franks, room
2-241 (in non-pandemic times).

**Office hours:** Mon 6:30p-8p and Wed 11a-12p, or by appointment, via Zoom and/or explain.mit.edu. The room 2-147 is reserved 11a-12:30 Wed for on-campus students to meet if they wish.

**TA:** Alexey Balitskiy, Room 2-231A, office hour: 5:30-7 pm Thursday.

**Prerequisites:** Linear algebra. Exposure to discrete
mathematics (18.200) is a plus, as well as exposure to algorithms
(6.006 and 18.410).

**Textbook:** There is no required textbook. Lecture
notes will be distributed during the term. For additional references,
the following textbooks are recommended (roughly in increasing difficulty
level or comprehensiveness). The last two are especially recommended
to anyone interested in a recent, in-depth coverage of the subject.

- J. Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.
- W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization.
- C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
- E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
- G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
- B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2012. Available online with MIT certificates.
- 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.

**Assignments and grading.**

**Psets:**There will be roughly bi-weekly problem sets. Students will be grouped into teams to facilitate pset collaboration, but must write up their own work. There will be designated Zoom rooms and slack channels for psetting, and the course is also active on pset partners . There might be additional questions on psets for graduate students, and undergraduates can earn a small number of bonus points for completing these problems. Problem sets will be submitted through the Gradescope tool in Canvas. Graduate students and undergraduates may be graded differently. When possible, psets will be due**11:00 pm Thursday nights.**-
**Quiz:**There will be a timed quiz**Thursday April 1**(replacing class). -
**Final:**There will be a timed final**(date TBD)**.

** Problem Sets:**
Hand these in using the **Gradescope** tool in Canvas. Please label your pages carefully.

- Problem set 1, due 11:00 pm Thurs 3/04/2021.
- Problem set 2, due 11:00 pm Thurs 3/18/2021.
- Problem set 3, due 11:00 pm
**Mon**4/12/2021. (Extended) - Problem set 4, due 11:00 pm
**Mon**4/26/2021. (Extended) - Problem set 5, due 11:00 pm Thurs 5/13/2021.
- Practice quiz

**Syllabus:** (preliminary version)

- Introduction.
- Cardinality bipartite matching.
- Efficiency of algorithms.
- Assignment problem.
- Non-bipartite matching.
- Polytopes, linear programming, geometry.
- Polyhedral combinatorics.
- Maximum flow problem.
- Minimum cut problems.
- The ellipsoid algorithm.
- The matching polytope.
- Matroids. Matroid optimization, matroid polytope.
- Matroid intersection.
- Arborescence problem.
- Matroid union.
- Perfect graphs.

**Instructor notes:**

- Lecture 1: Introduction; matching, spanning trees, and spin glasses.
- Lecture 2: Cardinality bipartite matching; König's theorem.
- Lecture 3: Minimum weight matching; primal-dual algorithm.
- Lectures 4 and 5: Non-bipartite matching; Tutte-Berge Theorem and Edmonds' algorithm.
- Lecture 6: Polyhedra, Fourier-Motzkin elimination, Farkas' Lemma.
- Lecture 7: Linear programming duality.
- Lecture 8: Faces of polyhedra, Krein-Milman Theorem.
- Lecture 9: Minimal descriptions of polyhedra, local picture of vertices.
- Lecture 10: Caratheodory's Theorem, Total unimodularity.
- Lecture 11: Non-bipartite matching polytope.
- Lecture 12: Max-flow min-cut.
- Lecture 13: Edmonds-Karp algorithm, Global min-cut.
- Lecture 14: Stoer-Wagner algorithm, Min T-odd cut.
- Lecture 15: Matroid optimization.
- Lecture 16: Matroid polytope; primal-dual proof.
- Lecture 17: Matroid polytope; vertex integrality proof.
- Lecture 18-19: Matroid intersection; largest common independent set.

**Source materials:**

- From Lecture 1 on 2/16/2019:
- Bipartite matching notes
- Lecture notes on maximum matchings in general graphs
**(Edmonds' algorithm clarified)** - Lecture notes on linear programming and polyhedral combinatorics
- Lecture notes on maximum flows
- Lecture notes on matroids
- Lecture notes on matroid intersection
- Matroid intersection activity
- Lecture notes on the ellipsoid algorithm