18.438: Advanced Combinatorial Optimization, Spring 2012
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"
also available as
(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,
- 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.
- 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.
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.