## [ 514 - Network Optimization]

### Lecturer: Thomas Rothvoss

- Office: Padelford C-440

- Office hours:
Monday 10:30AM-11:30AM and Wednesday 11:30PM-12:30PM

- Email: rothvoss@uw.edu

### Course information

- Class schedule:
**MWF 9:30 - 10:20**in**PDL C401**

**Description**:

**Lecture notes**:

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

- There will be daily reading assignments from the book. I will cover essentials but many of the details and discussions will be left as reading assignments.
- Your grade will be based on homework assignments. Homeworks are due weekly on Fridays in class. I will post a few problems after each lecture. The last set of problems on a given homework will be posted after the Monday lecture of the week in which the homework is due.
- NO EXAMS

### Homework

**Homework I, due Friday, October 3 in class.**

Please solve 1.7, 1.9, 10.1 in Schrijver's notes.**Homework II, due Friday, October 10 in class.**

Please solve 2.2, 2.4, 2.6(ii), 2.16 in Schrijver's notes**Homework III, due Monday, October****20 in class.**

Please solve 2.26, 2.27, 3.3, 3.5 (Hint: for 3.5, set up a bipartite graph and prove the claim using Theorem 3.3)**Homework IV, due Friday, Oct 24 in class.**

Please solve 3.11 , 3.17, 3.25, 8.4**Homework V, due Friday, Oct 31 in class.**

Please solve 8.6, 8.7, 8.14, 4.5

Remark: One direction of 8.6 is a bit harder --- you should apply Cor 8.2a at some point.**Homework VI, due Friday, Nov 7 in class.**

Please solve 4.7 (ii) [you don't need to give the intermediate steps, just the final flow + cut], 4.9, 4.10

Also solve the following: Consider a directed graph D = (V,A) with capacities c(a) on the arcs, a source s and a sink t. Let F be the value of the maximum s-t flow, let n be the number of nodes and m be the number of arcs. Show that there exists an s-t path on which all edges have capacity at least F/(2*m).

Optional: Use this insight to give a polynomial time algorithm for the maximum flow problem.**Homework VII, due Monday, Nov 17 in class.**

Please solve 4.15, 5.1, 5.7 (ii), 5.23

Please read chapter 5.1-5.4 (Non-bipartite matching without Cunningham-marsh formula) in Schrijver's notes. For a "less-compact" description of the cardinality matching algorithm, you can also look at Chapter 7 here.

Since I am travelling,**Jon Swenson**will give an**office hour**to answer questions. He will be available on Friday,**Nov 14, 1:30-2:30**in**C-406**.**Homework VIII (last homework), due Wednesday, Dec 3 in class.**

Please solve the 3 exercises at the end of the MaxCut chapter in the lecture notes.

### Course calendar

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

- Wednesday, Sep 24: Chapter 1.4 (spanning trees)
- Friday, Sep 26: Chapter 1.4 (spanning trees)
- Monday, Sep 29: Chapter 10.1 (matroids)
- Wednesday, Oct 1: Chapter 10.1 (matroids) + Chapter 2.1
- Friday, Oct 3: Chapter 2.1
- Monday, Oct 6: Chapter 2.2+2.3

Reading assignment: Please read Cor 2.5a+Cor2.5b - Wednesday, Oct 8: Chapter 2.4 (strong duality theorem)

Reading assignment: Please read the remainder of Chapter 2.

- Friday, Oct 10: Chapter 3.1 (stable sets, vertex covers, matchings, edge covers)
- Monday, Oct 13: Chapter 3.2+3.3 (M-augmenting paths, Koenig's Theorem)
- Wednesday, Oct 15: Chapter 3.4 (algorithm for cardinality
matching in bipartite graphs)

- Friday, Oct 17: Chapter 3.6

Reading assignment: Please read chapter 3.5 - Monday, Oct 20: Chapter 8.1
- Wednesday, Oct 22: Chapter 8.2
- Friday, Oct 24: Chapter 8.3 (TU matrices for bipartite
graphs)

Reading assignment: Please read the rest of chapter 8.3 - Monday, Oct 27: Chapter 4.2 (flows)
- Wednesday, Oct 29: Max Flow algorithm
- Friday, Oct 31: Max Flow algorithm (part II), Applications of flows (this part is not in Schrijver's notes. See this file)
- Monday, Nov 3: Min Cost Flows

- Wednesday, Nov 5: Hoffman's Circulation Theorem (Chapter
4.5)

- Friday, Nov 7: Computing min-cost flows (Chapter 4.6); non-bipartite matching (Chapter 5.1)
- Monday, Nov 10: I'm traveling. Please read Chapter 5.1-5.4
- Wednesday, Nov 12: I'm traveling. Please read Chapter 5.1-5.4
- Friday, Nov 14: I'm traveling. Please read Chapter 5.1-5.4
- Monday, Nov 17: MaxCut (lecture notes)
- Wednesday, Nov 19: MaxCut (part II) and Interior point Method. See the excellent lecture notes of Michel Goemans (starting at page 22).
- Friday, Nov 21: Interior point method (part II). See chapter 2 in my lecture notes
- Monday, Nov 23: Interior point method (part III). See chapter 2 in my lecture notes
- Wednesday, Nov 25: Finished Interior point method.

- Monday, Dec 1: Matroid intersection (see chapter 3 in my lecture notes)