Course description:
This is a graduate-level course in combinatorial optimization with a focus on polyhedral characterizations. In the first part of the course, we will cover some classical results in combinatorial optimization: algorithms and polyhedral characterizations for matchings, spanning trees, matroids, and submodular functions. In the second part, we will cover some more recent work that builds upon these techniques - algorithms using the primal-dual scheme, iterated rounding and dependent randomized rounding. I am also planning to cover some recent lower bounds on the complexity of LP descriptions of certain combinatorial polytopes.
Prerequisites:
Students should know basic computation theory, linear programming, and the notion of NP-completeness.
Grading:
There will be bi-weekly homeworks which constitute 50%. A take-home final exam will count for the remaining 50%.
In addition, students will be asked to scribe some lectures in LaTeX. I have notes for the first part of the course but not all of it. Writing up one lecture allows you to skip one homework. Reading material: