## [ 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.

### 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).