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.
Students should know basic computation theory, linear programming, and the notion of NP-completeness.
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: