[ 514 - Networks and Combinatorial Optimization ]

Winter 2018

Lecturer: Thomas Rothvoss

Teaching Assistant: Daiwei He

Course information

Homework

  1. Homework I, due Friday, Jan 12 in class.
    Please solve 1.7, 1.9, 10.1 in Schrijver's notes
  2. Homework II, due Friday, Jan 19 in class.
    Please solve 2.2, 2.4, 2.5 in Schrijver's notes.
  3. 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.

  1. Wednesday, Jan 3: Chapter 1.4 started with spanning trees
  2. Friday, Jan 5: finished correctness proof of Prim/Kruskal. Application to maximum reliability problem
  3. Monday, Jan 8: Chapter 10.1. Introduction to matroids
  4. Wednesday, Jan 10. Finished matroids. Started with Chapter 2 and finished Hyperplane Separation Theorem.
  5. Friday, Jan 12. Characterization of vertices of polyhedra. Introduction of cones. Finished with first direction of Farkas Lemma.
  6. Monday, Jan 15. NO CLASS (MLK Day)
  7. Wednesday, Jan 17: Finished proof of Farkas Lemma. Showed that bounded LPs attain optimum.
  8. Friday, Jan 19: Duality Theorem for Linear Programming. Started with Chapter 3 (definitions).
Last day of class will be Friday, Mar 9, 2018.