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:301:40pm in Padelford
C440
 TA:
 Nathan Cheung, ncheung@uw.edu. Office hour: Thursday 12:30
 1:30pm in PDL C111.
 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
realworld 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,
PrenticeHall, 19 82.
 B. Korte and J. Vygen, Combinatorial Optimization:
Theory and Algorithms, Algorithms and Combinatorics 21
Springer, Berlin Heidelberg New York, 2006.
 3volume book by A. Schrijver, Combinatorial
Optimization: Polyhedra and Efficiency,
SpringerVerlag, 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.
 Wednesday, Sep 27, 2023. Graphs and minimum spanning trees
 Monday, Oct 2, 2023. Correctness of DijkstraPrim and Kruskal,
Maximum Reliability problem. Matroids.
 Wednesday, Oct 4, 2023. Matroid greedy algorithm. Chapter 3
until the end of proof of Hyperplane Separation Theorem.
 Monday, Oct 9, 2023. Characterization of extreme points of
polyhedra.
 Wednesday, Oct 11, 2023. Farkas Lemma and more on linear
programming.
 Monday, Oct 16, 2023. Strong Duality. Beginning of Chapter on
Matchings in Bipartite Graphs until Maugmenting paths.
 Wednesday, Oct 18, 2023. Chapter 4  Koenig's Theorem. Chapter
5 until Def of integer polyhedron.
 Monday, Oct 23: Chapter 5 continuation until TU matrices from
bipartite graphs.
 Wednesday, Oct 25: Finished Chapter 5 (skipped the 2nd
direction of the Theorem of GhouilaHouri). Started with Chapter
6.
 Monday, Oct 30: MaxFlow MinCut
 Wednesday, Nov 1: Elimination of Sports Teams, Parts of the
proof of Hoffman's circulation Theorem.
 Monday, Nov 6: RECORDED VIDEO  Finishing proof of Hoffman's
circulation Theorem. Matchings in general graphs (Part I)
 Wednesday, Nov 8: RECORDED VIDEO  Matchings in general
graphs (Part II)
 Monday, Nov 13: Chapter 6.4+6.5 on MinCost Flows. Then
Interior Point Methods
 Wednesday, Nov 15: Interior point methods (until overview).
 Monday, Nov 20: Interior point methods (starting with the
analysis of the Newton step)
 Wednesday, Nov 22: Finishing Interior Point Methods. Then
Chapter 10.1 and 10.2
 Monday, Nov 27: Chapter 10.3+
 Wednesday, Nov 29: Finished Capter 10 (SDPs). Started with
Chapter 6.6. (The Minimum Mean Cycle algorithm)
 Monday, Dec 4: The Minimum Mean Cycle algorithm (cont.)
 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')
You can check your points on the GradeScope webpage.
Corrections to the lecture notes
This is the first iteration that I am using this set of lecture
notes. I plan continuously update the PDF to remove any typos and
mistakes. I will post details on the updates here:
 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 > nonsingular. 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 TutteBerge 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 2dim 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 2dim instance
for MaxCut