Topics in combinatorial optimization

Lectures: 2 sessions / week, 1.5 hours / session

In this graduate-level course, we will be covering advanced topics in combinatorial optimization. We will start with non-bipartite matchings and cover many results extending the fundamental results of matchings, flows and matroids. The emphasis is on the derivation of purely combinatorial results, including min-max relations, and not so much on the corresponding algorithmic questions of how to find such objects (although we will be discussing a few algorithmic issues, such as minimizing submodular functions). The course will rely heavily on the recent 3-volume textbook by Lex Schrijver on Combinatorial Optimization. The intended audience consists of Ph.D. students interested in optimization, combinatorics, or combinatorial algorithms.

Students taking this course should have had prior exposure to combinatorial optimization, for example, by taking 18.433 (Combinatorial Optimization ) or a similar course. This course assumes knowledge of bipartite matchings, spanning trees, and similar basic notions in combinatorial optimization.

The grade assigned is based on students preparing scribe notes of the lectures and on class participation. The job of the scribe is to prepare a good set of lecture notes based on what was covered in lecture and additional readings.

Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. New York, NY: Springer-Verlag, 2003. ISBN: 3540443894.

The textbook is the 3-volume book, but we will be covering only some of the 83 chapters. This is a marvelous book with lots of results, references and concise proofs. I will assume familiarity with many basic results in combinatorial optimization.

Here is a preliminary (and partial) list of topics to be discussed:

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare