Dr. Annie Raymond,
TA and Grader:
Topics to be covered:
computational complexity, matchings in bipartite graphs and in general graphs, assignment problem, polyhedral combinatorics, total unimodularity, matroids, matroid intertersection, min arborescence, max flow/min cut, max cut, traveling salesman.
There are no required textbooks. We will rely mostly on lecture notes which Michel Goemans (MIT) and Thomas Rothvoss (UW) very generously provided; they will be posted below as they become relevant. For additional information, I recommend the following textbooks:
This course requires a good working knowledge of Math 407 (linear programming) and Math 308 (linear algebra). The material covered in these two courses will be assumed to be familiar to students throughout this course. Please review these materials if you took these classes a while ago.
The grade will be a convex combination of the performance in the submitted problem sets (20%), the midterm (30%) and the final (50%).
Lecture notes from Michel Goemans (MIT), Thomas Rothvoss (UW), and myself: