- Class schedule: MWF
12:30 - 1:20 in JHN175

- Instructor:

Thomas Rothvoss, rothvoss@uw.edu.

Office hour: We 10:00am - 11:00am in Padelford C440 **TAs:**

- Joseph David, jdavid5@uw.edu. Office hour: Tuesdays
1pm-2pm on Zoom (https://washington.zoom.us/j/92344808073)

- Ravil Mussabayev, ravmus@uw.edu. Office hour: Friday 9am-10am on Zoom (https://washington.zoom.us/j/94705022020)

- Joseph David, jdavid5@uw.edu. Office hour: Tuesdays
1pm-2pm on Zoom (https://washington.zoom.us/j/92344808073)
**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 course requires a good working knowledge of Math 407 (Linear Programming) and Math 308 (Linear Algebra).

**Grading**: The grade will be a convex combination of the performance in the submitted problem sets (20%; lowest scoring assignment is dropped), the mid term exam (30%) and the final exam (50%).**Problem sets:**Problem sets will be posted each Friday; due date is the following Friday 11pm via GradeScope.

**Late policy**: GradeScope will accept submissions until Monday 11pm. Every student is allowed 5 late days in total. So you are allowed to submit for example 5 assignments up to 24h late or one assignment 3 days late and another one 2 days late. No prior approval required. Simply submit to GradeScope when you are done. If you submit late and you are out of late days the submission counts 0.

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

**Lecture notes**for the course are available here**Discussion forum:**Other than in office hours, you may ask questions on course content and homework on the course discussion forum on Piazza.

- Monday, Mar 28, 2022: Course logistics; Section 1.1 Algorithms and Complexity; Section 1.1.1 Complexity theory and NP-hardness
- Wednesday, Mar 30, 2022: Section 1.2 Graph Theory (undirected graphs)
- Friday, April 1, 2022: Section 1.2 Graph Theory (directed graphs) and Section 1.3 TSP
- Monday, April 4, 2022: Section 2 Minimum Spanning Trees (finished with Def of connected components)
- Wednesday, April 6, 2022: Section 2 Minimum Spanning Trees (finished)
- Friday, April 8, 2022: Shortest Paths (until beginning of correctness proof of Dijkstra's algorithm)
- Monday, April 11: Shortest Paths (correctness proof of Dijkstra's algorithm; Moore-Bellman-Ford algorithm)
- Wednesday, April 13: Correctness of Moore-Bellman-Ford. Detecting of negative cost cycles.
- Friday, April 15: Finding negative cost cycle. Introduction to Network Flows.
- Monday, April 18: Residual graphs, Ford-Fulkerson, s-t MinCut
is upper bound on MaxFlow

- Wednesday, April 20: Proof of MaxFlow=MinCut Theorem.
Edmonds-Karp algorithm

- Friday, April 22: Running time analysis of Edmonds-Karp
- Monday, April 25: Bipartite matchings, Koenigs Theorem
- Wednesday, April 27: Hall's Theorem. Started with linear
programming chapter (polyhedra, convexity, convex hull)

- Friday, April 29: Cont. linear programming
- Monday, May 2: Farkas Lemma
- Wednesday, May 4: MIDTERM
- Friday, May 6: Strong Duality Theorem. Discussion of LP
algorithms (skipped the section on the gradient-descent based
method)

- Monday, May 9: Connection of LPs to discrete optimization.
Integer programs and integer hull (skipped the direct proof of
the integrality of the bipartite matching LP, Lemma 48)

- Wednesday, May 11: Intro to total unimodularity
- Friday, May 13: Criterion for checking TU'ness. Application to bipartite matching
- Monday, May 16: Application to flows. TUness of node-edge incidence matrices of directed graphs. TUness of matrices with consecutive-ones property
- Wednesday, May 18: Finished TU chapter. Begin Branch &
Bound chapter.

- Friday, May 20: Finished B & B chapter. Started with matchings in general graphs
- Monday, May 23: Augmenting paths for matchings
- Wednesday, May 25: Contracting M-blossoms
- Friday, May 27: Finished chapter on matchings in non-bipartite graphs. Started chapter on Knapsack problem
- Monday, May 30: NO CLASS --- MEMORIAL DAY
- Wednesday, June 1: A dynamic program for Knapsack. A (1-epsilon)-approximation algorithm for Knapsack
- Friday, June 3: OFFICE HOUR IN JHN175

- Homework 1. Due: Friday, April 8, 11pm on GradeScope.
- Homework 2. Due: Friday, April 15, 11pm on GradeScope.
- Homework 3. Due: Friday, April 22, 11pm on GradeScope.
- Homework 4. Due: Friday, April 29, 11pm on GradeScope.
- Homework 5. Due: Friday, May 13, 11pm on GradeScope.
- Homework 6. Due: Friday, May 20, 11pm on GradeScope.
- Homework 7. Due: Friday, May 27, 11pm on GradeScope.
- Homework 8.
Due: Friday, June 3, 11pm on GradeScope.

- Wednesday, May 4, 2022, in class, i.e. 12:30-1:20pm in JHN 175. You may bring one sheet of notes (printed on one side or handwritten on both sides).

- Thursday, June 9, 2022, 8:30am - 10:20am in JHN 175. You may bring one sheet of notes (printed on one side or handwritten on both sides).

- "
*Combinatorial Optimization*" by Cook, Cunningham,Pulleyblank, Schrijver: Contains most topics that are also covered in class (plus many more). A very readable, though quite expensive book.

*"Computational complexity"*by*Arora and Barak:*State of the art book for complexity theory. From the topics covered in class, this book contains only the small complexity part. A preliminary version is available for free here.

- Chapter 1: Def spanning tree: Added that T is subgraph of G.
Def directed graph: Added "i != j". Number of tours in a
complete undirected graph is 1/2*(n-1)! and not (n-1)! For
Stirling approximation replaced 2^.. by e^.. For TSP added n
>= 3.

- Chapter 2: Before Lemma 3: replaced "more than 2 paths" ->
"more than one path"

- Chapter 3: Expanded the alternative exposition of the
correctness proof of Dijkstra's algorithm. Lemma 16: some
"paths" are "walks" and a "cycle" is a "closed walk" . Also
cleaned up what n means in this context. Added footnote to
Dijkstra and MBF correctness covering the case that some node is
not reachable from s.

- Chapter 4: Lemma 21: added ``gamma >= 0''. In Def of flow augmentation need to change f(e^-1) instead of f(e) for backward edges. Replaced the proof that augmenting flow along P indeed gives a feasible s-t flow. Removed the (t,a) edge in the example. In correctness proof of Edmonds-Karp, one index i' changed to i.
- Chapter 5. Replace $x = A_I^{-1}x$ by $x = A_I^{-1}b_I$ in description of simplex. Cleaned up other linear algebra expressions in the simplex section. Replaced "circuit" by "cycle". Fixed the example 2-dim. LP.
- Chapter 6. Added detail in TU'ness of
matrices with consecutive-ones property. Cor 56 b) label
should be c)

- Chapter 7. First constraint in B & B example should be -4x_1 + 6x_2 <= 9 instead of -x_1 + 6x_2 <= 9
- Chapter 8. Added condition to Def of
M-flower. Some smaller tweaks throughout the chapter. In Lemma
72+73 added that B should be M-blossom (was only implicit
before). Expanded proof of Lemma 73 and added two figures.