47-853 Special Topics in Combinatorial Optimization

6 units, Carnegie Mellon University

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.

Prerequisites: none listed

Offered: Fall 2026, Spring 2026

Courseweave needs JavaScript to show sections, workloads and planning tools.