[ 514 - Network Optimization]

Lecturer: Thomas Rothvoss

Course information

Homework

  1. Homework I, due Friday, October 3 in class.
    Please solve 1.7, 1.9, 10.1 in Schrijver's notes.
  2. Homework II, due Friday, October 10 in class.
    Please solve 2.2, 2.4, 2.6(ii), 2.16 in Schrijver's notes
  3. Homework III, due Monday, October 20 in class.
    Please solve 2.26, 2.27, 3.3, 3.5 (Hint: for 3.5, set up a bipartite graph and prove the claim using Theorem 3.3)
  4. Homework IV, due Friday, Oct 24 in class.
    Please solve 3.11 , 3.17, 3.25, 8.4
  5. Homework V, due Friday, Oct 31 in class.
    Please solve 8.6, 8.7, 8.14, 4.5
    Remark: One direction of 8.6 is a bit harder --- you should apply Cor 8.2a at some point. 
  6. Homework VI, due Friday, Nov 7 in class.
    Please solve 4.7 (ii) [you don't need to give the intermediate steps, just the final flow + cut], 4.9, 4.10
    Also solve the following: Consider a directed graph D = (V,A) with capacities c(a) on the arcs, a source s and a sink t. Let F be the value of the maximum s-t flow, let n be the number of nodes and m be the number of arcs. Show that there exists an s-t path on which all edges have capacity at least F/(2*m).
    Optional: Use this insight to give a polynomial time algorithm for the maximum flow problem. 
  7. Homework VII, due Monday, Nov 17 in class.
    Please solve 4.15, 5.1, 5.7 (ii), 5.23
    Please read chapter 5.1-5.4 (Non-bipartite matching without Cunningham-marsh formula) in Schrijver's notes. For a "less-compact" description of the cardinality matching algorithm, you can also look at Chapter 7 here.
    Since I am travelling, Jon Swenson will give an office hour to answer questions. He will be available on Friday, Nov 14, 1:30-2:30 in C-406.
  8. Homework VIII (last homework), due Wednesday, Dec 3 in class.
    Please solve the 3 exercises at the end of the MaxCut chapter in the lecture 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, Sep 24: Chapter 1.4 (spanning trees)
  2. Friday, Sep 26: Chapter 1.4 (spanning trees)
  3. Monday, Sep 29: Chapter 10.1 (matroids)
  4. Wednesday, Oct 1: Chapter 10.1 (matroids) + Chapter 2.1
  5. Friday, Oct 3: Chapter 2.1
  6. Monday, Oct 6: Chapter 2.2+2.3
    Reading assignment: Please read Cor 2.5a+Cor2.5b
  7. Wednesday, Oct 8: Chapter 2.4 (strong duality theorem)
    Reading assignment: Please read the remainder of Chapter 2.
  8. Friday, Oct 10: Chapter 3.1 (stable sets, vertex covers, matchings, edge covers)
  9. Monday, Oct 13: Chapter 3.2+3.3 (M-augmenting paths, Koenig's Theorem)
  10. Wednesday, Oct 15: Chapter 3.4 (algorithm for cardinality matching in bipartite graphs)
  11. Friday, Oct 17: Chapter 3.6
    Reading assignment: Please read chapter 3.5
  12. Monday, Oct 20: Chapter 8.1
  13. Wednesday, Oct 22: Chapter 8.2
  14. Friday, Oct 24: Chapter 8.3 (TU matrices for bipartite graphs)
    Reading assignment: Please read the rest of chapter 8.3
  15. Monday, Oct 27: Chapter 4.2 (flows)
  16. Wednesday, Oct 29: Max Flow algorithm
  17. Friday, Oct 31: Max Flow algorithm (part II), Applications of flows (this part is not in Schrijver's notes. See this file)
  18. Monday, Nov 3: Min Cost Flows
  19. Wednesday, Nov 5: Hoffman's Circulation Theorem (Chapter 4.5)
  20. Friday, Nov 7: Computing min-cost flows (Chapter 4.6); non-bipartite matching (Chapter 5.1)
  21. Monday, Nov 10: I'm traveling. Please read Chapter 5.1-5.4
  22. Wednesday, Nov 12: I'm traveling. Please read Chapter 5.1-5.4
  23. Friday, Nov 14: I'm traveling. Please read Chapter 5.1-5.4
  24. Monday, Nov 17: MaxCut (lecture notes)
  25. Wednesday, Nov 19: MaxCut (part II) and Interior point Method. See the excellent lecture notes of Michel Goemans (starting at page 22).
  26. Friday, Nov 21: Interior point method (part II). See chapter 2 in my lecture notes
  27. Monday, Nov 23: Interior point method (part III). See chapter 2 in my lecture notes
  28. Wednesday, Nov 25: Finished Interior point method.
  29. Monday, Dec 1: Matroid intersection (see chapter 3 in my lecture notes)
Last day will be Friday, Dec 5, 2014.