18.438: Advanced Combinatorial Optimization, Fall 2009
Tuesdays and Thursdays 9:30AM-11:00AM in 2-135. First meeting Sept 10th,
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
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"
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,
- J.G. Oxley, "Matroid Theory", Oxford University Press, 1992.
List of problems (updated Nov 24, 2009).
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.