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:
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.
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.
A few papers on matchings beyond what was covered in class (possible topics for term project):
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).
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.