## [ 514 - Networks and Combinatorial Optimization ]

### Winter 2018

### 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:
Daiwei He

**Office hour:**Tuesday 2pm-3pm in PDL C-8B

### Course information

- Class schedule:
**MWF 9:30 - 10:20**in SMI 309 (Smith Hall; first class is Wednesday, Jan 3)

**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, Jan 12 in class.**

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

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

Please solve 2.16, 2.26, 2.27 in Schrijver's notes.**Homework IV, due Friday,****Feb 2 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, Feb 9 in class.**

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

Please solve 8.8, 8.9, 4.15 in Schriver's notes.**Homework VII, due Friday, Feb****23 in class.**

Please solve 5.1, 5.2, 5.4 in Schrijver's notes.**Homework VIII, due Friday,****Mar 2 in class.**

Please solve the 2 exercises at the end of the interior point lecture notes.**Homework IX, due Friday, Mar 9 in class.**

Please solve 10.5, 10.19, 10.22 in Schrijver's exercises

### 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, Jan 3: Chapter 1.4 started with spanning trees
- Friday, Jan 5: finished correctness proof of Prim/Kruskal. Application to maximum reliability problem
- Monday, Jan 8: Chapter 10.1. Introduction to matroids
- Wednesday, Jan 10. Finished matroids. Started with Chapter 2 and finished Hyperplane Separation Theorem.
- Friday, Jan 12. Characterization of vertices of polyhedra. Introduction of cones. Finished with first direction of Farkas Lemma.
- Monday, Jan 15. NO CLASS (MLK Day)
- Wednesday, Jan 17: Finished proof of Farkas Lemma. Showed that bounded LPs attain optimum.
- Friday, Jan 19: Duality Theorem for Linear Programming. Started with Chapter 3 (definitions).
- Monday, Jan 22: Koenig's Theorem

- Wednesday, Jan 24: Finishing Ch. 3 with the matching
polytope.

- Friday, Jan 26: Starting with Chapter 8: Def TU, Proof that polyhedra with TU constraint matrices are integer.
- Monday, Jan 29: Hoffman-Kruskal Theorem
- Wednesday, Jan 31: Intro to flows
- Friday, Feb 2: MaxFlow MinCut

- Monday, Feb 5: Residual vgraphs, MaxFlow algorithm
- Wednesday, Feb 7: Hoffman's Circulation Theorem
- Friday, Feb 9: Min Cost Flows
- Monday, Feb 12: Ch 5.: Matching in non-bipartite graphs
- Wednesday, Feb 14: Finding M-alternating walks, M-blossoms
- Friday, Feb 16: Finished Edmond's cardinality matching algorithm. Started with Path-Following Interior Point Methods.
- Monday, Feb 19: NO CLASS (Presidents Day)
- Wednesday, Feb 21: Interior point method
- Friday, Feb 23: Interior point method
- Monday, Feb 26: Matroid intersection
- Wednesday, Feb 28: Matroid intersection
- Friday, Mar 2: Matroid intersection