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.

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