18.455: Advanced Combinatorial Optimization, Spring 2020

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.
• Problem Set 3, due 4/30/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.