Schedule
This is a log of what was actually done.
Aug 22 Syllabus, What is linear programming and few small examples. Notes Diet in APmonitor
Aug 24 Graphically solving linear program and basic definitions Notes Ropes in APmonitor
Aug 26 Guest Lecture by Jan Foniok about trains and platforms
Aug 29 Introduction to Duality of LP Notes
Aug 31 Interpretation of Duality Notes Separation Theorem Notes
Sep 2 no class
Sep 5 Labour day
Sep 7 Graph Theory Review (by Kacy) Notes
Sep 9 more Graph Theory
Sep 12 Farkas Lemma Notes
Sep 14 Consequences of Duality Notes
Sep 16 Simplex Method Notes
Sep 19 Klee-Minty Cube and Ellipsoid Method Notes
Sep 21 Interior Point Methods Notes
Sep 23 Minimum Spanning Tree Notes
Sep 26 Minimum Spanning Tree
Sep 28 Shortest Path Notes
Sep 30 Shortest Path
Oct 3 Shortest Path and linear programming Notes
Oct 5 Network Flows - first introduction Notes
Oct 7 Network Flows
Oct 10 Network Flows - first algorithm Notes
Oct 12 Network Flows - faster algorithms Notes
Oct 14 Network Flows
Oct 17 no class
Oct 19 no class
Oct 21 no class
Oct 24 Minimum cut
Oct 26 Gomory-Hu trees Notes
Oct 28 Gomory-Hu trees
Oct 31 Phylogenetics Trees - Guest lecture by
Nov 2 Minimum Cost Flow Notes
Nov 4 Minimum Mean Cycle Notes
Nov 7 Integer Programming - Unimodular Matrices Notes
Nov 9 Integer Programming - More Unimodular Matrices
Nov 11 Integer Programming - Branch and Bound Notes
Nov 14 Integer Programming - Cutting Planes Notes
Nov 16 Matching Edmonds Notes
Nov 18 Matching
Nov 21 Thanks giving
Nov 23 Thanks giving
Nov 25 Thanks giving
Nov 28 Minimum-cost perfect matching in bipartite graph Notes
Nov 30 Goemans-Williamson 1 Notes
Dec 2 Goemans-Williamson 2
Dec 5 TSP Notes
Dec 7 no class
Dec 9 SDP and Max-cut (starts 8:00am) Notes Notes
Dec 12 (7:30am-9:30am) Final Exam