[ 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.
  4. 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.
  5. 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 
  6. Homework VI, due Friday, Feb 16 in class.
    Please solve 8.8, 8.9, 4.15 in Schriver's notes.
  7. Homework VII, due Friday, Feb 23 in class.
    Please solve 5.1, 5.2, 5.4 in Schrijver's notes.
  8. Homework VIII, due Friday, Mar 2 in class.
    Please solve the 2 exercises at the end of the interior point lecture notes.
  9. 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.

  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).
  9. Monday, Jan 22: Koenig's Theorem
  10. Wednesday, Jan 24: Finishing Ch. 3 with the matching polytope.
  11. Friday, Jan 26: Starting with Chapter 8: Def TU, Proof that polyhedra with TU constraint matrices are integer.
  12. Monday, Jan 29: Hoffman-Kruskal Theorem
  13. Wednesday, Jan 31: Intro to flows
  14. Friday, Feb 2: MaxFlow MinCut
  15. Monday, Feb 5: Residual vgraphs, MaxFlow algorithm
  16. Wednesday, Feb 7: Hoffman's Circulation Theorem
  17. Friday, Feb 9: Min Cost Flows
  18. Monday, Feb 12: Ch 5.: Matching in non-bipartite graphs
  19. Wednesday, Feb 14: Finding M-alternating walks, M-blossoms
  20. Friday, Feb 16: Finished Edmond's cardinality matching algorithm. Started with Path-Following Interior Point Methods. 
  21. Monday, Feb 19: NO CLASS (Presidents Day)
  22. Wednesday, Feb 21: Interior point method
  23. Friday, Feb 23: Interior point method
  24. Monday, Feb 26: Matroid intersection
  25. Wednesday, Feb 28: Matroid intersection
  26. Friday, Mar 2: Matroid intersection
Last day of class will be Friday, Mar 9, 2018.