18.455: Advanced Combinatorial Optimization, Spring 2020

Instructor: Michel Goemans.

Tuesdays and Thursdays 9:30AM-11:00AM in 4-149.

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

Office hour: by appointment (easiest, ask in class; ow, by email).

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 around 5 problem sets.

• Problem set 1, due 2/27/2020. (Updated. Hint in exercise 3 has been corrected.)

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).