514 - Networks and Combinatorial Optimization - Fall 2023

Course information

• Class schedule: MW 10:00 - 11:20 in SMI 404
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: TBD in Padelford C440
  
• TA:
  
  • 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. 
• Lecture notes for the course are available here here.
  Much of these notes is based on the excellent lectures notes written by Lex Schrijver that you can find here. You may consult those additional background. 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.
• 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 (TBD).
  
• Collaboration policy: You are allowed (in fact encouraged) to discuss the homework problems in groups. However, you are required to write up solutions on your own. Absolutely identical submission will be considered as a violation of this policy.
• Late policy: If you cannot make the due date (and time) please let me know so we can find an agreement. 
  
• Religious accommodations: You may find the university policy here.
  

Covered material

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.

1. Wednesday, Sep 27, 2022. Graphs and minimum spanning trees

Last day of class will be Wednesday, Dec 6, 2023.

Problem sets

• Homework 1, due Friday, Oct 6, 11pm on GradeScope: TBD
  

Corrections to the lecture notes

• TBD
•