Math 409 - Spring 2016

Lecturer:
Dr. Annie Raymond,
raymonda(_at_)uw.edu
Padelford C-432

TA and Grader:
Daniel Bragg
braggdan(_at_)uw.edu
Padelford C-8-F

Office hours:

• Monday 9:20-10:20 in Annie's office
• Monday 12:30-13:20 in Annie's office (or LOW 219 if ever too crowded) for the problem session
• Friday 11:30-12:30 in Annie's office
• Friday 13:00-14:00 in Daniel's office
• If you can't make it then, email me for an appointment.

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.

Textbook:
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:

• Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schriver
• Combinatorial Optimization: Polyhedra and Efficiency by Schrijver
• Combinatorial Optimization: Theory and Algorithms by Korte and Vygen

Prerequisites:
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.

Grading:
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:

• Disability Resources for Students
• Student Counseling Center
  

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

• 03/28: algorithms and complexity (TR)
• 03/30 and 04/01: matchings for bipartite graphs (MG)
• 04/04: stable marriage problem (AR)
• 04/06 and 04/08: assignment problem (MG)
• 04/11 through 04/15: matchings in general graphs (MG)
• 04/17: linear programming (TR)
• 04/19 and 04/21: more linear programming (MG)
• 04/25: review
• 04/27: midterm
• 04/29: example of technique 2 (AR)
• 05/02: all techniques + example of technique 3 (MG)
• 05/04: total unimodularity (MG)
• 05/06: matroids introduction (MG)
• 05/09 and 05/11: matroids optimization and rank (MG)
• 05/13 through 05/23: the matroid polytope (MG)
• 05/25 through 06/01: max flow/min s,t-cut (MG)

Homework:

• Homework 1 - due 04/04 at the beginning of class
• Homework 2 - 04/11
• Homework 3 - 04/18
• Homework 4 - 04/25
• Homework 5 - 05/09
• Homework 6 - 05/16
• Homework 7 - 05/23
• Homework 8 - 06/01