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: We 12:30-1:40pm in Padelford C440
  
• TA:
  
  • Nathan Cheung, ncheung@uw.edu. Office hour: Thursday 12:30 - 1:30pm in PDL C-111.
    
• 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 (see link send to mailing list).
  
• 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, 2023. Graphs and minimum spanning trees
2. Monday, Oct 2, 2023. Correctness of Dijkstra-Prim and Kruskal, Maximum Reliability problem. Matroids.
   
3. Wednesday, Oct 4, 2023. Matroid greedy algorithm. Chapter 3 until the end of proof of Hyperplane Separation Theorem.
4. Monday, Oct 9, 2023. Characterization of extreme points of polyhedra.
5. Wednesday, Oct 11, 2023. Farkas Lemma and more on linear programming.
6. Monday, Oct 16, 2023. Strong Duality. Beginning of Chapter on Matchings in Bipartite Graphs until M-augmenting paths.
7. Wednesday, Oct 18, 2023. Chapter 4 - Koenig's Theorem. Chapter 5 until Def of integer polyhedron.
8. Monday, Oct 23: Chapter 5 continuation until TU matrices from bipartite graphs.
   
9. Wednesday, Oct 25: Finished Chapter 5 (skipped the 2nd direction of the Theorem of Ghouila-Houri). Started with Chapter 6.
10. Monday, Oct 30: MaxFlow MinCut
11. Wednesday, Nov 1: Elimination of Sports Teams, Parts of the proof of Hoffman's circulation Theorem.
12. Monday, Nov 6: RECORDED VIDEO --- Finishing proof of Hoffman's circulation Theorem. Matchings in general graphs (Part I)
    
13. Wednesday, Nov 8: RECORDED VIDEO --- Matchings in general graphs (Part II)
14. Monday, Nov 13: Chapter 6.4+6.5 on MinCost Flows. Then Interior Point Methods
15. Wednesday, Nov 15: Interior point methods (until overview).
16. Monday, Nov 20: Interior point methods (starting with the analysis of the Newton step)
17. Wednesday, Nov 22: Finishing Interior Point Methods. Then Chapter 10.1 and 10.2
18. Monday, Nov 27: Chapter 10.3+
19. Wednesday, Nov 29: Finished Capter 10 (SDPs). Started with Chapter 6.6. (The Minimum Mean Cycle algorithm)
20. Monday, Dec 4: The Minimum Mean Cycle algorithm (cont.)
21. Wednesday, Dec 6: Concluded strongly polynomial bound on Minimum Mean Cycle algorithm (Tardos)
    

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

Problem sets

• Homework 1, due Friday, Oct 6, 11pm on GradeScope.
• Homework 2, due Friday, Oct 13, 11pm on GradeScope.
• Homework 3, due Friday, Oct 20, 11pm on GradeScope.
• Homework 4, due Friday, Oct 27, 11pm on GradeScope.
• Homework 5, due Friday, Nov 3, 11pm on GradeScope.
• Homework 6, due Friday, Nov 10, 11pm on GradeScope.
• Homework 7, due Friday, Nov 17, 11pm on GradeScope.
• Homework 8, due Friday, Dec 1, 11pm on GradeScope. (updated on Nov 22; the D in 6.4.(i) needs to be D')
  

Corrections to the lecture notes

• Oct 4, 2023. Chapter 1: minor typos. Chapter 2. I -> mathcal{I}, = w(Z) -> <= w(Z) in proof of Theorem 2.6. Chapter 3: edited figure in Hyperplane Separation Theorem 
  
• Oct 10, 2023. Chapter 2: slightly simplified the proof that Y_i is a basis of {e_1,...,e_i}. Chapter 3: {n \choose m} -> {m \choose n}. regular -> non-singular. Fixed minor typos.
• Oct 25, 2023: Fixed a few typos in Chapter 5 and 6.
• Oct 27, 2023: Added problems 5.2 and 5.3
• Nov 1, 2023: Chapter 6: In proof of MaxFlow=MinCut, at some point f and f' were mixed up. Some typos. Chapter 7: Added explicit description of Edmonds algorithm.
• Nov 6, 2023: Chapter 6: In the alternative proof of MaxFlow=MinCut, an index v had to be t.
• Nov 15, 2023: Chapter 7: The min in the first inline formula in the proof of the Tutte-Berge formula had to be a max. Chapter 8: One constant 1/24 should be 1/64.
  
• Nov 20, 2023: Chapter 8: Typo in the first Lemma 8.4 (the gradient includes t*c*h)
• Nov 22, 2023: Chapter 6: The D in Exercise 6.4.(i) needs to be D'. Chapter 10: Updated figure of K. In 2-dim example, 4 had to be a 5.
• Nov 24, 2023: Chapter 6: Some arrows in the worst case example for Ford Fulkerson had wrong directions.
• Dec 7, 2023: Chapter 10: Index i missing in the 2-dim instance for MaxCut