Instructor: Michel Goemans.

Tuesdays and Thursdays 9:30AM-11:00AM. Was in 4-149, and now in zoom.

This page: https://math.mit.edu/18.455

Office hour: by appointment or here

In this course, we will be covering a range of topics in combinatorial optimization. A partial/preliminary list of topics include:

- Non-bipartite matchings: Tutte-Berge formula, Edmonds' algorithm, Edmonds-Gallai decomposition, etc.
- Matchings: Algebraic approaches, Pfaffians, Pfaffian orientations, counting perfect matchings in planar graphs.
- Matching polytope, total-dual integrality (TDI), compact formulations and extension complexity.
- Stable sets: perfect graphs, weak perfect graph theorem, stable set polytope.
- Stable sets: orthonormal representations, theta function and Shannon capacity. Semidefinite Programming (SDP).
- Matroids: representability, matroid intersection, matroid matching, approximately counting bases.
- Submodularity. Minimization.
- Multi-commodity flows and disjoint paths.

** Assignments.** There will be at most 4 problem sets.

- Problem set 1, due 2/27/2020. (Updated. Hint in exercise 3 has been corrected.)
- Problem Set 2, due 4/14/2020 on gradescope.

** Textbook and lecture notes.** The best reference on the subject is the 3-volume book by Lex
Schrijver "Combinatorial Optimization: Polyhedra and Efficiency"
(available in the libraries) published
by Springer. This is optional (as I don't follow it closely). I will try my best to provide some lecture notes (often from past scribed notes from students).

- Lecture notes for first 3 lectures on maximum cardinality matchings in general graphs (Tutte-Berge formula, Edmonds algorithm, Edmonds-Gallai decomposition, ear decompositions).
- Lecture notes on an algebraic approach for matchings (determinant of skew-symmetric matrices, Pfaffians, blue-red matchings, Pfaffian orientations, counting matchings in planar graphs).
- Lecture notes on the matching polytope and Total Dual Integrality
- Lecture notes from Jan Vondrak on extended formulations and extension complexity and lower bound on the extension complexity for the correlation polytope.
**Matroids.**Matroid definitions and representability. Matroid optimization, matroid intersection (algorithm and min-max relation), matroid intersection polytope and matroid union, matroid partition algorithm and base covering and packing.