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