Carnegie Mellon University

Special Topics: Combinatorial Optimization

Course Number: 47853

Menger (1927) showed that the maximum number of disjoint st-paths is equal to the minimum cardinality of an st-cut. Dilworth (1950) proved that the minimum number of chains needed to cover a poset is equal to the maximum cardinality of an antichain. These classic results are what started the field of Packing and Covering. In this course, we will see many theorems of this form, and study the underlying graph theoretic and geometric attributes that lead to such min-max and max-min results.

Degree: PhD
Concentration: Operations Research
Academic Year: 2019-2020
Semester(s): Mini 3
Required/Elective: Elective
Units: 6


Lecture: 100min/wk and Recitation: 50min/wk


Students may find Gerard Cornuejols’ book titled “Combinatorial Optimization: Packing and Covering” as well as the instructor’s notes titled “Packing and Covering” helpful (available on their personal webpages).

Learning Objectives

Students will have a better knowledge of foundational theorems in Combinatorial Optimization.