18.438: Advanced Combinatorial Optimization, Fall 2009

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


List of problems (updated Nov 24, 2009).

Schedule and Notes