MATH 233B: Polyhedral techniques in combinatorial optimization

Stanford University, Winter 2017

Lectures: Tue/Thu 10:30 - 11:50 am, McCullough 126
Instructor: Jan Vondrak
Office hours: by appointment

Lecture notes:
(Note: Lectures 14-20 are here in the logical order rather than in the order they were presented in class.)

Sample file for scribes

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: