Courses:

When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

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.

Prerequisites

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.

Grading

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.

Textbook

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.

Topics

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

• Ear decompositions
• Nonbipartite matching
• Gallai-Milgram and Bessy-Thomasse theorems on partitioning/covering graphs by directed paths/cycles
• Minimization of submodular functions
• Matroid intersection, Polymatroid intersection
• Jump systems
• Matroid union
• Matroid matching, path matchings
• Packing trees and arborescences
• Packing directed cuts and the Lucchesi-Younger theorem
• Submodular flows and the Edmonds-Giles theorem
• Graph orientation
• Connectivity tree and connectivity augmentation
• Multicommodity flows