514 - Networks and Combinatorial Optimization - Fall 2023

Course information

Covered material

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.

  1. Wednesday, Sep 27, 2023. Graphs and minimum spanning trees
  2. Monday, Oct 2, 2023. Correctness of Dijkstra-Prim and Kruskal, Maximum Reliability problem. Matroids.
  3. Wednesday, Oct 4, 2023. Matroid greedy algorithm. Chapter 3 until the end of proof of Hyperplane Separation Theorem.
  4. Monday, Oct 9, 2023. Characterization of extreme points of polyhedra.
  5. Wednesday, Oct 11, 2023. Farkas Lemma and more on linear programming.
  6. Monday, Oct 16, 2023. Strong Duality. Beginning of Chapter on Matchings in Bipartite Graphs until M-augmenting paths.
  7. Wednesday, Oct 18, 2023. Chapter 4 - Koenig's Theorem. Chapter 5 until Def of integer polyhedron.
  8. Monday, Oct 23: Chapter 5 continuation until TU matrices from bipartite graphs.
  9. Wednesday, Oct 25: Finished Chapter 5 (skipped the 2nd direction of the Theorem of Ghouila-Houri). Started with Chapter 6.
  10. Monday, Oct 30: MaxFlow MinCut
  11. Wednesday, Nov 1: Elimination of Sports Teams, Parts of the proof of Hoffman's circulation Theorem.
  12. Monday, Nov 6: RECORDED VIDEO --- Finishing proof of Hoffman's circulation Theorem. Matchings in general graphs (Part I)
  13. Wednesday, Nov 8: RECORDED VIDEO --- Matchings in general graphs (Part II)
  14. Monday, Nov 13: Chapter 6.4+6.5 on MinCost Flows. Then Interior Point Methods
  15. Wednesday, Nov 15: Interior point methods (until overview).
  16. Monday, Nov 20: Interior point methods (starting with the analysis of the Newton step)
  17. Wednesday, Nov 22: Finishing Interior Point Methods. Then Chapter 10.1 and 10.2
  18. Monday, Nov 27: Chapter 10.3+
  19. Wednesday, Nov 29: Finished Capter 10 (SDPs). Started with Chapter 6.6. (The Minimum Mean Cycle algorithm)
  20. Monday, Dec 4: The Minimum Mean Cycle algorithm (cont.)
  21. Wednesday, Dec 6: Concluded strongly polynomial bound on Minimum Mean Cycle algorithm (Tardos)

 Last day of class will be Wednesday, Dec 6, 2023.

Problem sets

 You can check your points on the GradeScope webpage.

Corrections to the lecture notes

This is the first iteration that I am using this set of lecture notes. I plan continuously update the PDF to remove any typos and mistakes. I will post details on the updates here: