514 - Networks and Combinatorial Optimization - Fall 2022

Course information

• Class schedule: MW 9:30 - 10:50 in RAI 116
  
• Instructor:
  Thomas Rothvoss, rothvoss@uw.edu.
  Office hour: We 12:00pm - 1:00pm in Padelford C440 (updated on Nov 11)
  
• TA:
  
  • 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. 
• Lecture notes: 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.
  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.

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

1. Wednesday, Sep 28, 2022. Chapter 1.4 -- minimum spanning trees
2. Monday, Oct 3, 2022: Chapter 1.4 -- maximum reliability; Chapter 10.1 -- matroids
3. Wednesday, Oct 5, 2022: Chapter 2.1 - convex sets; Chapter 2.2 until the fact that every polyhedron has a finite number of vertices.
4. Monday, Oct 10, 2022: Chapter 2.2 convex cones; Chapter 2.3 Farkas Lemma
5. Wednesday, Oct 12, 2022: Chapter 2.4 strong duality theorem. Chapter 3.1 + 3.2.
   
6. Monday, Oct 17, 2022: Chapter 3.3 Koenig's Theorem. Algorithm for maximum cardinality bipartite matching.
7. Wednesday, Oct 19, 2022: End of Chapter 3. Chapter 8.1 Integer Linear Programming
8. Monday, Oct 24, 2022: Chapter 8.2 Hoffman-Kruskal Theorem
9. Wednesday, Oct 26: Chapter 4.2 Flows in networks
10. Monday, Oct 31: Chapter 4.3. Finding a maximum flow. Chapter 4.5 Circulations
11. Wednesday, Nov 2: Chapter 4.5 Circulations. Chapter 4.6 Min Cost Flows
12. Monday, Nov 7: Chapter 4.6 Algorithm for Min Cost Flows; Chapter 5 Matchings in non-bipartite graphs
13. Wednesday, Nov 9: Chapter 5.1 proof of the Tutte-Berge formula; Chapter 5.2 Cardinality matching
14. Monday, Nov 14: Chapter 5.2 Cardinality matching. Chapter 10.4/10.5 matroid intersection (exchange lemma)
    
15. Wednesday, Nov 16: Chapter 10.4/10.5 matroid intersection (reverse exchange lemma)
16. Monday, Nov 21: Chapter 10.5 matroid intersection (the augmentation algorithm). Interior point method (preliminaries)
    
17. Wednesday, Nov 23: NO CLASS
18. Monday, Nov 28: Interior point method (Newton step analysis)
19. Wednesday, Nov 30: Interior point method. Positive semidefinite matrices.
20. Monday, Dec 5: The MaxCut SDP
21. Wednesday, Dec 7: Grothendieck / Krivine's Inequality
    

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

Additional material

• Matroid intersection (notes of Thomas following Schrijver's Chapter 10.4+10.5)
• Interior point methods (notes of Thomas following Bubeck's monograph Ch 5.3)
• Semidefinite programming (slides of Thomas)
  

Problem sets

• Homework 1, due Friday, Oct 7, 11pm on GradeScope: Please solve exercises 1.7 and 1.9 in Schrijver's notes.
• Homework 2, due Friday, Oct 14, 11pm on GradeScope: Please solve exercises 10.1, 10.2 and 2.1 in Schrijver's notes.
• Homework 3, due Saturday, Oct 22, 11pm on GradeScope: Please solve the problems on the PDF.
• Homework 4, due Friday, Oct 28, 11pm on GradeScope: Please solve exercises 3.3, 3.5 and 3.11 in Schrijver's notes.
• Homework 5, due Friday, Nov 4, 11pm on GradeScope: Please solve the exercises on the PDF.
• Homework 6, due Friday, Nov 11, 11pm on GradeScope: Please solve the exercises on the PDF.
• Homework 7, due Friday, Nov 18, 11pm on GradeScope: Please solve the exercises on the PDF.
• Homework 8, due Friday, Dec 2, 11pm on GradeScope: Please solve exercises 5.2, 5.4 and 5.23 in Schrijver's notes.
• Homework 9, due Friday, Dec 9, 11pm on GradeScope: Please solve exercises 10.22 and 10.26 in Schrijver's notes.