- Class schedule: MW
9:30 - 10:50 in RAI 116

- Instructor:

Thomas Rothvoss, rothvoss@uw.edu.

Office hour: We 11:00am - 12:00pm in Padelford C440 **TA:**

- Catherine Babecki, cbabecki@uw.edu. Office hour: TBD

- Catherine Babecki, cbabecki@uw.edu. Office hour: TBD
**Course description: Topics to be covered**: computational complexity, minimum spanning trees, shortest paths, max flow problems, min cost flow problems, matchings, traveling salesman problem, integrality of polytopes.-
**Prerequisites**: This is a graduate class on the fundamentals of network optimization / combinatorial optimization. The majority of these problems involve finding the 'best' candidate among a set of objects associated with a network/directed graph. Many of these problems come from real-world applications and as such it is important to solve large instances of these problems in practice. Therefore, along with understanding the mathematical structure of the problems, we will also be interested in the algorithms for solving them and the complexity/difficulty of these algorithms from a computer science point of view. This is a rigorous mathematical introduction to network optimization with proofs. Students are expected to solve mainly theoretical along with some practical problems as part of the homework. The lectures will follow the excellent notes written by Lex Schrijver that you can find here. For some chapters, I might provide my own lecture notes later.**Lecture notes**:

In case you want to read additional material, some of the popular books on combinatorial optimization are as follows:

- J. Lee,
*A First Course in Combinatorial Optimization*, Cambridge University Press, 2004. - W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver,
*Combinatorial Optimization*. - C. Papadimitriou and K. Steiglitz,
*Combinatorial Optimization*: Algorithms and Complexity, Prentice-Hall, 19 82. - B. Korte and J. Vygen,
*Combinatorial Optimization: Theory and Algorithms*, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2006. - 3-volume book by A. Schrijver,
*Combinatorial Optimization*: Polyhedra and Efficiency, Springer-Verlag, 2003.

- J. Lee,
**Required Work:**

- Your grade will be based on homework assignments. Homeworks are due weekly on Fridays on GradeScope. I will post homework problems on this webpage. Homework due in a particular week will be posted on Friday the week before (occasionally the posted homework will contain a problem based on material covered in the upcoming Monday lecture).
- Students are expected to read the lecture notes in parallel to the lecture.
- NO EXAMS

**Discussion forum:**Other than in office hours, you may ask questions on course content and homework on the course discussion forum on Piazza.

**To read before the quarter starts**: Chapter 6 in
Schrijver's notes on "Problems, Algorithms and Running Times".
Chapter 6 is essential for the whole course and can be read
independently of all other chapters. It will also help to read
Chapter 1 before the quarter starts (skip section 1.2). This
chapter is relatively easy and many students may have seen the
material already in an undergraduate class.

- Wednesday, Sep 28, 2022: Chapter 1.4 starting with spanning trees

Last day of class will be Wednesday, Dec 7, 2022.

- Homework 1, due Friday, Oct 7, 11pm on GradeScope. TBD.