18.438: Advanced Combinatorial Optimization, Spring 2012

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

Problem Sets:

Notes