18.438: Advanced Combinatorial Optimization, Spring 2014

Instructor: Michel Goemans.

Tuesdays and Thursdays 9:30AM-11:00AM in E17-122. First meeting Feb 3rd, 2014.

In this course, we will be covering advanced topics in combinatorial optimization. The course will be similarly structured to the one offered two years ago, although some of the topics will change; 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 stable sets and perfect graphs, matroids (representability, intersection, matching, applications, ...), submodularity, connectivity, multicommodity flows, nowhere zero flows, Hilbert bases, etc.

Textbook: The optional textbook is the 3-volume book by Lex Schrijver "Combinatorial Optimization: Polyhedra and Efficiency" (available at Barker and Hayden libraries) published by Springer-Verlag (they used to sell it also as a CD, available at Barton library). This is a marvelous book with lots of results, references and concise proofs. Other books covering some of these topics include:

Assignments, homework: There will be problem sets, and also from time to time, some readings for background material. There will be a term project consisting in describing and summarizing results from one (or a few) recent research papers.