Schedule
This is a log of what was actually done.
Aug 24 Class outline. Motivation for linear programming. notes APmonitor LP diet
Aug 26 Cutting ropes. Convex sets notes APmonitor LP for ropes APmonitor IP for ropes
Aug 28 Affine spaces
Aug 31 Radon and Helly theorem
Sep 2 Polytopes notes
Sep 4 Simplex notes
Sep 7 Labour day
Sep 9 Cyclic polytope, number of vertices and facets in the polytope
Sep 11 Separation theorem notes
Sep 14 Introduction to Duality notes
Sep 16 Interpretation of Duality and Duality theorem notes
Sep 18 Farkas Lemma and the proof of duality notes
Sep 21 Consequences of duality notes
Sep 23 Algorithms for Linear Programming notes
Sep 25 Simplex Algorithm notes
Sep 28 Interior point method notes
Sep 30 Spanning trees notes
Oct 2 Spanning trees
Oct 5 Shortest path notes
Oct 7 Shortest path and LP notes
Oct 9 Network flows intro notes
Oct 12 Network flows - first algorithm notes
Oct 14 Network flows - Menger's theorem
Oct 16 Network flows - faster algorithm notes
Oct 19 Network flows - and linear programming
Oct 21 Guest lecture by Jan Hubicka - compilers and graph algorithms
Oct 23 Gomory-Hu trees notes
Oct 26 Gomory-Hu trees
Oct 28 Gomory-Hu trees
Oct 30 Minimum Cost Flow notes
Nov 2 Minimum Mean Cycle notes
Nov 4 Minimum Mean Cycle
Nov 6 Integer programming - Unimodular matrices notes
Nov 9 Integer programming - Unimodular matrices
Nov 11 Integer programming - Branch and Bound notes
Nov 13 Integer programming - Cutting Planes notes
Nov 16 More Cutting planes, Matchings notes
Nov 18 Matching notes
Nov 20 Matching
Nov 23 Thanks giving
Nov 25 Thanks giving
Nov 27 Thanks giving
Nov 30 Matroids notes
Dec 2 Matroids
Dec 4 No class
Dec 7 Matroids
Dec 9 TSP
Dec 11 No class
Dec 16 Final Exam