[ 514 - Networks and Combinatorial Optimization ]

Fall 2016

Lecturer: Thomas Rothvoss

Teaching Assistant: Scott Roy

Course information

Homework

  1. Homework I, due Friday, October 7 in class.
    Please solve 1.7, 1.9, 10.1 in Schrijver's notes
  2. Homework II, due Friday, October 14 in class.
    Please solve 2.2, 2.4, 2.5 in Schrijver's notes
  3. Homework III, due Friday, October 21 in class.
    Please solve 2.16, 2.26, 2.27 in Schrijver's notes.
  4. 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.
  5. 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. 
  6. 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 
  7. 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.  
  8. Homework VIII, due Monday, Nov 28 in class.
    Please solve the 3 exercises at the end of this PDF file
  9. Homework IX, due Friday, Dec 2 in class.
    Please solve 5.1, 5.2, 5.4.
  10. 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.

  1. Wednesday, Sep 28: Chapter 1.4 (spanning trees)
  2. Friday, Sep 30: Cont. spanning trees
  3. Monday, Oct 3: Matroids
  4. Wednesday, Oct 5: Chapter 2: Convex sets
  5. Friday, Oct 7: Chapter 2: Vertices, Convex cones, statement of Farkas Lemma
  6. Monday, Oct 10: Chapter 2: Proof of Farkas Lemma 
  7. Wednesday, Oct 12: Linear programs
  8. Friday, Oct 14: Proof of strong duality
  9. Monday, Oct 17: Chapter 3.1+3.2: Matchings and augmenting paths
  10. Wednesday, Oct 19: Chapter 3.3: Koenig's Theorem
  11. Friday Oct 21: Cardinality bipartite matching algorithm and Weighted bipartite matching algorithm
  12. Monday, Oct 24: (Perfect) matching polytope. TU Matrices.
  13. Wednesday, Oct 26: Cont. TU matrices
  14. Friday, Oct 28: Proof of Hoffman-Kruskal Theorem.
  15. Monday, Oct 31: Koenig's Theorem via TU matrices
  16. Wednesday, Nov 2: Flows until Pro 2, value(f) <= cut(U) for any s-t cut
  17. Friday, Nov 4: Proof of MaxFlow=MinCut Theorem
  18. Monday, Nov 7: Ford-Fulkerson algorithm for MaxFlow
  19. Wednesday, Nov 9: Edmonds-Karp algorithm. Beginning of Sports team elimination
  20. Monday, Nov 14: Sports team elimination via max flows (see this PDF file)
  21. Wednesday, Nov 16: Circulations and Hoffman's Theorem
  22. Friday, Nov 18: The minimum cost circulation problem
  23. Monday, Nov 21: Cycle cancelling algorithm and node potentials
  24. Wednesday, Nov 23: Finished analysis of the cycle cancelling algorithm
  25. Monday, Nov 28: Matchings in non-bipartite graphs
  26. Wednesday, Nov 30: Proof of the Tutte-Berge Formula
  27. Friday, Dec 2: M-blossoms
  28. Monday, Dec 5: Finished Edmonds blossom algorithm
  29. Wednesday, Dec 7: Matroid intersection
  30. Friday, Dec 9: Matroid intersection
Last day of class will be Friday, Dec 9, 2016.