18.455: Advanced Combinatorial Optimization, Spring 2020
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.
Multi-commodity flows and disjoint paths.
Assignments. There will be at most 4 problem sets.
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.