## [ 514 - Networks and Combinatorial Optimization ]

### Fall 2016

### Lecturer: Thomas Rothvoss

- Office: Padelford C-440

- Office hours:
Monday 10:30 - 11:30 and Wednesday 10:30 - 11:30

- Email: rothvoss@uw.edu

### Teaching Assistant: Scott Roy

**Office hour:**Thursdays 4-5 in PDL C-8D

### Course information

- Class schedule:
**MWF 9:30 - 10:20**in DEM 112 (we are using this room starting on Wednesday, Oct 5, 2016)

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

- Your grade will be based on homework assignments. Homeworks are due weekly on Fridays in class. I will post homework problems on this webpage. Typically, 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.
- Students are expected to read the lecture notes in parallel to the lecture.
- NO EXAMS

### Homework

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

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

Please solve 2.2, 2.4, 2.5 in Schrijver's notes**Homework III, due Friday, October 21 in class.**

Please solve 2.16, 2.26, 2.27 in Schrijver's notes.**Homework IV, due Friday, October****28****in class.**

Please solve 3.3, 3.5, 3.11 (Hint: for 3.5, set up a bipartite graph and prove the claim using Theorem 3.3) in Schrijver's notes.**Homework V****, due Friday, November 4 in class.**

Please solve 8.6, 8.9, 8.14

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

Please solve 4.5, 4.7 (i) (no need to write out all steps of the algo), 4.9**Homework VII, due Friday, Nov****18 in class.**

Solve 4.10, 4.12. Additionally solve the following exercise:

Given a directed graph D = (V,A) with s,t in V and integer capacities u : A -> Z. Run the Ford-Fulkerson algorithm to compute a maximum s-t flow, but each time select that flow-augmenting path P that maximizes the capacity of its bottleneck edge. Prove that the algorithm finds the maximum flow after at most O(m * log( value of maxflow )) many iterations.**Homework VIII, due Monday, Nov 28 in class.**

Please solve the 3 exercises at the end of this PDF file.**Homework IX, due Friday,****Dec 2 in class.**

Please solve 5.1, 5.2, 5.4.**Homework X (last homework), due Friday, Dec 9 in class**.

Please solve the 3 exercises at the end of this PDF file.

### 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 28: Chapter 1.4 (spanning trees)
- Friday, Sep 30: Cont. spanning trees
- Monday, Oct 3: Matroids
- Wednesday, Oct 5: Chapter 2: Convex sets
- Friday, Oct 7: Chapter 2: Vertices, Convex cones, statement of Farkas Lemma
- Monday, Oct 10: Chapter 2: Proof of Farkas Lemma
- Wednesday, Oct 12: Linear programs

- Friday, Oct 14: Proof of strong duality

- Monday, Oct 17: Chapter 3.1+3.2: Matchings and augmenting
paths

- Wednesday, Oct 19: Chapter 3.3: Koenig's Theorem
- Friday Oct 21: Cardinality bipartite matching algorithm and Weighted bipartite matching algorithm
- Monday, Oct 24: (Perfect) matching polytope. TU Matrices.
- Wednesday, Oct 26: Cont. TU matrices
- Friday, Oct 28: Proof of Hoffman-Kruskal Theorem.
- Monday, Oct 31: Koenig's Theorem via TU matrices

- Wednesday, Nov 2: Flows until Pro 2, value(f) <= cut(U)
for any s-t cut

- Friday, Nov 4: Proof of MaxFlow=MinCut Theorem
- Monday, Nov 7: Ford-Fulkerson algorithm for MaxFlow
- Wednesday, Nov 9: Edmonds-Karp algorithm. Beginning of Sports team elimination
- Monday, Nov 14: Sports team elimination via max flows (see
this PDF
file)

- Wednesday, Nov 16: Circulations and Hoffman's Theorem
- Friday, Nov 18: The minimum cost circulation problem

- Monday, Nov 21: Cycle cancelling algorithm and node potentials
- Wednesday, Nov 23: Finished analysis of the cycle cancelling algorithm
- Monday, Nov 28: Matchings in non-bipartite graphs
- Wednesday, Nov 30: Proof of the Tutte-Berge Formula

- Friday, Dec 2: M-blossoms
- Monday, Dec 5: Finished Edmonds blossom algorithm
- Wednesday, Dec 7: Matroid intersection
- Friday, Dec 9: Matroid intersection