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.

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