18.438: Advanced Combinatorial Optimization, Fall 2009

Instructor: Michel Goemans.

Tuesdays and Thursdays 9:30AM-11:00AM in 2-135. First meeting Sept 10th, 2009.

In this course, we will be covering advanced topics in combinatorial optimization. The course will be an updated, expanded and hopefully improved (!) version of a class offered 5 years ago. Scribe notes and other material from that class are available here on OCW. 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 matroids (representability, intersection, matching, applications, ...), submodularity, connectivity, multicommodity flows, nowhere zero flows, Hilbert bases, etc.

Textbook: The recommended textbook is the 3-volume book by Lex Schrijver "Combinatorial Optimization: Polyhedra and Efficiency" (published by Springer-Verlag; also available as a CD). This is a marvelous book with lots of results, references and concise proofs. I will also use chapters from other books, including

• L. Lovasz and M.D. Plummer, "Matching Theory", North-Holland, 1986.
• J.G. Oxley, "Matroid Theory", Oxford University Press, 1992.

Problems

Schedule and Notes

• Sept 10, 2009. Introduction + maximum matchings (Tutte-Berge formula). Refs: Schrijver, chap 24.
  Scribe notes from the 2004 version.
• Sept 15, 2009. Maximum matchings (Edmonds algorithm, Edmonds-Gallai decomposition). Refs: Schrijver, chap 24.
  Scribe notes by Alex Levin.
• Sept 17, 2009. Maximum matchings (Edmonds-Gallai decomposition, factor-critical graphs) + ear decompositions (2-(edge)-connectivity, factor criticality). Refs: Schrijver, chaps 24, 28 and 15.5; Lovasz and Plummer.
  Scribe notes by Aleksander Madry.
• Sept 22, 2009. Cubic graphs, edge-colorings. Nowhere zero flows. Refs: Schrijver, chap 28; Seymour, "Nowhere zero flows", in Handbook of Combinatorics, Volume 1, Eds. R. Graham, M. Groetchel and L. Lovasz, 1995.
  Scribe notes by Yufei Zhao.
• Sept 24, 2009. Nowhere zero flows.
  Scribe notes by Yehua Wei.
• Sept 29, 2009. Matching polytope, Total Dual Integrality (TDI). Refs: Schrijver, sections 5.17, 5.18, 25.2, 25.3.
  Scribe notes by Debmalya Panigrahi.
• Oct 1, 2009. No class.
• Oct 6, 2009. TDI (cont'd) and Cunningham-Marsh formula for matchings.
  Scribe notes by David Sontag.
• Oct 8, 2009. Matroids. Refs: Schrijver, chap 39.
  Scribe notes by Elette Boyle.
• Oct 13, 2009. No class (Monday schedule).
• Oct 15, 2009. Matroid representability.Refs: Oxley's book.
  Scribe notes by Shashi Mittal.
• Oct 20, 2009. Matroid intersection. Refs: Schrijver, chaps 40, 41.
  Scribe notes by Anthony Kim.
• Oct 22, 2009. Matroid intersection (alg, min-max relation).
  Scribe notes by Jacob Steinhardt.
• Oct 27, 2009. Matroid intersection polytope, matroid union. Refs: Schrijver, chap 42.
  Scribe notes by Chung Chan.
• Oct 29, 2009. Matroid partition algorithm. Base (and spanning trees) packing and covering. Shannon's switching game. Refs: Schrijver, chaps 42 and 51.
  Scribe notes by Alan Deckelbaum.
• Nov 3, 2009. Shannon and Lehman's switching game. Refs: A. Lehman, "A solution to Shannon's switching game", J. Soc. Indust. Appl. Math, vol 12, 1964.
  Scribe notes by Xin Lu.
• Nov 5, 2009. Matroid matching. Refs: Schrijver, chap. 43.
  Scribe notes by Paul Christiano.
• Nov 10, 2009. Graph orientations via matroid intersection. Refs: Schrijver, chap. 61.
  Scribe notes by Jose Soto.
• Nov 12, 2009. Graph orientations via splitting-off. Submodular function minimization.
  Scribe notes by Juliane Dunkel.
• Nov 17, 2009. Submodular function minimization. Algorithm by Iwata and Orlin, 2009.
  Scribe notes by Claudio Telha Cornejo.
• Nov 19, 2009.
  Scribe notes by Ankur Moitra.
• Nov 24, 2009. Okamura-Seymour theorem and the Wagner-Weihe linear time algorithm. Refs: Schrijver, chapter 74, and Wagner and Weihe's paper.
  Preliminary scribe notes (to be reviewed).
• Dec 1, 2009. Clutters (ideal, MaxFlowMinCut property, blockers, etc), packing.
  Scribe notes by Elette Boyle.
• Dec 3, 2009.
• Dec 8, 2009.
• Dec 10, 2009.