Math 409 - Spring 2016

University of Washington, Seattle
MWF 10:30-11:20PM in SMI 305
Midterm: 04/27 in class
Final: 06/06 from 8:30AM to 10:20AM

Dr. Annie Raymond,
Padelford C-432

TA and Grader:
Daniel Bragg
Padelford C-8-F

Office hours:

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%).

Other resources:

Lecture notes from Michel Goemans (MIT), Thomas Rothvoss (UW), and myself: