MWF 10:30-11:20PM in SMI 305

Midterm: 04/27 in class

Final: 06/06 from 8:30AM to 10:20AM

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

**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