Combinatorial Optimization

The course will cover a series of topics in combinatorial optimization focusing on good characterizations via min-max theorems. The emphasis will be on polyhedral theory and structural results. Some specific topics to be covered are: Matchings, T-joins, Matroids, Matroid intersection, Submodular functions, Polymatroids, Arborescences, Branchings, Directed cuts, Multi-flows.

Mathematical maturity at the level of a graduate student will be assumed. Familiarity with reading and writing mathematical proofs is required. Prior coursework in Linear Programming and Graph Theory will be helpful.


The following is a tentative list of lectures. Subject to change.