18.438: Advanced Combinatorial Optimization, Spring 2012

Instructor: Michel Goemans.

Tuesdays and Thursdays 11:00AM-12:30PM in 2-151. First meeting Feb 7th, 2012.

No class on Tuesday May 17th. Makeup classes on Friday April 20th, April 27th and May 4th from 10:30AM to 12 noon in 2-255.

In this course, we will be covering advanced topics in combinatorial optimization. The course will be similarly structured (with updates and improvements) to the one offered two years ago; 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 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 (which they have also at Barton library). This is a marvelous book with lots of results, references and concise proofs. Occasionally, I will also use other books, including

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

Problem Sets:

• Problem Set 1 due February 28th, 2012.
• Problem Set 2 due March 22nd, 2012.
• Problem Set 3 due April 12th, 2012.
• Problem Set 4 due May 1st, 2012.

Notes

• February 7, 9 and 14th, 2012. Intro. Maximum matchings (Tutte-Berge formula, Edmonds' algorithm, Edmonds-Gallai decomposition, factor-critical graphs). Ear-decompositions.
  Refs: Schrijver, chaps 24, 28 and 15.5; Lovasz and Plummer.
  Earlier scribe notes: Lec 1, lec 2, lec 3. See also notes from 18.433 on non-bipartite matchings.
• February 16th and February 28th, 2012. 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. Groetschel and L. Lovasz, 1995.
  Updated scribe notes: Lec 4 and lec 5
• Matching polytope, Total Dual Integrality (TDI), Cunningham-Marsh formula for matchings.
  Refs: Schrijver, sections 5.17, 5.18, 25.2, 25.3.
  Earlier scribe notes on Matching polytope, TDI, Hilbert bases and TDI and Cunningham-Marsh formula.
• Matroids.
  Refs: Schrijver, chap 39. Oxley's book (matroid representability). Schrijver, chaps 40, 41, 42, 51. Shannon and Lehman's switching game. A. Lehman, "A solution to Shannon's switching game", J. Soc. Indust. Appl. Math, vol 12, 1964. Schrijver Chapter 43.
  Earlier scribe notes on matroid definitions, on matroid representability, on matroid optimization and intersection, on matroid intersection (alg, min-max relation), on matroid intersection polytope, matroid union, on matroid partition algorithm, base (and spanning trees) packing and covering and Shannon's switching game, on Shannon's switching game (continued), on matroid matching.
• Graph orientations.
  Refs: Schrijver, chap. 61.
  Scribe notes on graph orientations via matroid intersection (Updated) or via splitting-off.
• Submodular Function minimization.
  Scribe notes: introduction and updated notes on Iwata-Orlin's algorithm.
• Disjoint paths and Multiflows.
  Scribe notes:Introduction and 2-commodity flows (new) and Okamura-Seymour and Wagner-Weihe for planar graphs with all terminals on one face.