18.438: Advanced Combinatorial Optimization, Spring 2014

Instructor: Michel Goemans.

Tuesdays and Thursdays 9:30AM-11:00AM in E17-122. First meeting Feb 3rd, 2014.

In this course, we will be covering advanced topics in combinatorial optimization. The course will be similarly structured to the one offered two years ago, although some of the topics will change; information for this last edition (with scribe notes) is available here. I will assume familiarity with many basic results in combinatorial optimization. I will start with non-bipartite matchings, and a non-exhaustive list of topics include stable sets and perfect graphs, matroids (representability, intersection, matching, applications, ...), submodularity, connectivity, multicommodity flows, nowhere zero flows, Hilbert bases, etc.

Textbook: The optional textbook is the 3-volume book by Lex Schrijver "Combinatorial Optimization: Polyhedra and Efficiency" (available at Barker and Hayden libraries) published by Springer-Verlag (they used to sell it also as a CD, available at Barton library). This is a marvelous book with lots of results, references and concise proofs. Other books covering some of these topics include:

• L. Lovasz and M.D. Plummer, "Matching Theory", North-Holland, 1986.
• J.G. Oxley, "Matroid Theory", Oxford University Press, 1992.
• B. Korte and J. Vygen, "Combinatorial Optimization: Theory and Algorithms", Springer, 2006.
• A. Frank, "Connections in Combinatorial Optimization", Oxford University Press, 2011.

Assignments, homework: There will be problem sets, and also from time to time, some readings for background material. There will be a term project consisting in describing and summarizing results from one (or a few) recent research papers.

• Problem set 1 due March 13th, 2014.
• Problem set 2 due April 15th, 2014.

Lectures.

• Matchings.

  Lectures on Feb 4, 6, 11 covered the maximum cardinality (non-bipartite) matching problem, including the Tutte-Berge formula, Edmonds' algorithm (with blossoms, etc), the Edmonds-Gallai decomposition, factor-critical graphs and their ear-decomposition. See Schrijver, chapter 24. Lecture notes from a past edition will be revised shortly.

  Lecture on Feb 13 covered an algebraic approach to matching, including a bijective proof of the relation between the determinant of a skew-symmetric matrix and its Pfaffian (see Godsil, Algebraic Combinatorics, 1993). Lecture on Feb 25 on Pfaffians orientations, and counting perfect matchings in planar graphs. Scribe notes for both lectures.

  Lecture on Feb 20 covered the matching polytope, TDIness and the Cunningham-Marsh formula.

  A few papers on matchings beyond what was covered in class (possible topics for term project):

  • A new proof of the correctness of the Micali-Vazirani algorithm for maximum cardinality matching by Vijay Vazirani.
  • Thomas Rothvoss' recent proof that the matching polytope requires exponentially many inequalities.
  • A characterization of the perfect matching lattice (the integral combinations of all perfect matchings) by Laci Lovasz.
  • Making an approach based on the Tutte matrix deterministic by Jim Geelen.
  • Finding maximum matchings in the time to multiply 2 matrices, by Nick Harvey.
  • Finding minimum-cost perfect matchings using cutting planes by Karthik Chandrasekaran, Laszlo Vegh and Santosh Vempala.
• Perfect graphs and stable sets.

  Scribe notes on definition, examples and repetition lemma. Scribe notes on the weak perfect graph theorem, orthonormal representations, theta function, Stable set polytope. Scribe notes on equivalent formulations of Theta function. SDP basics and SDP strong duality. Shannon capacity of graphs (notes missing).

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

  Graph orientations via matroid intersection and splitting-off.