Course MAT572

Introduction to Combinatorial Optimization

This course will survey the theory of combinatorial optimization. 

 

We will cover:

-The elementary min-max theorems of graph theory, such as   Konig's theorems and Tutte's matching theorem

-Network flows (Menger's theorem, the max-flow min-cut theorem, multicommodity flows)

-Linear programming and polyhedral optimization

-Hypergraph packing and covering problems

-Perfect graphs

-Polyhedral methods to prove min-max theorems

-Packing directed cuts, the Lucchesi-Younger theorem

-Packing T-cuts, T-joins and circuits

-Edmonds' matching polytope theorem

-Relations with the four-colour theorem

-Lehman's results on ideal clutters

-Various further topics (the ellipsoid method, the matching lattice, the theta-function) as time permits.

Placement and Prerequisites

Some familiarity with basic graph theory will be assumed.