MATH 233B: Polyhedral techniques in combinatorial optimization

Stanford University, Winter 2017

Lectures: Tue/Thu 10:30 - 11:50 am, McCullough 126
Instructor: Jan Vondrak
E-mail: jvondrak@stanford.edu
Office hours: by appointment

Lecture notes:

Lecture 1 : LP duality, optimization and separation
Lecture 2 : The bipartite matching polytope, Konig's theorem
Lecture 3 : Totally unimodular matrices
Lecture 4 : Non-bipartite matching, Tutte-Berge formula
Lecture 5 : The matching polytope
Lecture 6 : Weighted non-bipartite matching
Lecture 7 : Spanning trees and matroids
Lecture 8 : The greedy algorithm; rank and span in matroids.
Lecture 9 : Matroid duality; the matroid polytope
Lecture 10 : Matroid intersection
Lecture 11 : Matroid intersection algorithmically
Lecture 12 : Applications of matroid intersection
Lecture 13 : Matroid union
Lecture 14 : Submodular functions; the greedy algorithm
Lecture 15 : Continuous extensions of submodular functions
Lecture 16 : Submodular maximization subject to a matroid constraint
Lecture 17 : Extended formulations: the permutahedron and the spanning tree polytope
Lecture 18 : Lower bound for the correlation polytope
Lecture 19 : Lower bound for the matching polytope I
Lecture 20 : Lower bound for the matching polytope II

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

Sample file for scribes

Homework:

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:

Lex Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, 3-volume book, Springer, 2003.