COMBINATORIAL OPTIMIZATION
Schedule.
Week 1.
Monday September 3rd.
Holiday: No Lecture.
Wednesday September 5th.
Matchings: Edmonds Matching Algorithm.
Week 2.
Monday September 10th.
Shortest Paths: Bellman-Ford; Minimum Mean Cost Cycle.
Wednesday September 12th.
Maximum Flows: Disjoint Paths.
Week 3.
Monday September 17th.
Maximum Flows: Dinits' Algorithm; Bipartite Matchings.
[Assignment 1 assigned.]
Wednesday September 19th.
Minimum Cost Flows: Residual Graphs; Minimum Mean Cycle Augmentation.
Week 4.
Monday September 24th.
Matchings: the Matching Polytope.
Wednesday September 26th.
Linear Programming Duality: Primal-Dual Theorem.
[Assignment 1 due.]
Week 5.
Monday October 1st.
Linear Programming Duality: Shortest s-t Paths; Maxflow-Mincut theorem.
[Assignment 2 assigned.]
Wednesday October 3rd.
Guest Lecture.
Week 6.
Monday October 8th.
Thanksgiving: No Lecture
Tuesday October 9th.
Matchings: Weighted Bipartite Matchings.
Wednesday October 10th.
The Ellipsoid Method.
[Assignment 2 due.]
Week 7.
Monday October 15th.
Applications of the Ellipsoid Method: the Matching Problem; the Maximum Cut Problem.
[Assignment 3 assigned.]
Wednesday October 17th.
The Shortest
r
-Arborescence Problem.
Week 8.
Monday October 22nd.
Graph Connectivity: Minimum Cut.
Wednesday October 24th.
Graph Connectivity: Gomory-Hu Trees.
[Assignment 3 due.]
Week 9.
Monday October 29th.
T-Joins; T-Cuts.
[Assignment 4 assigned.]
Wednesday November 31st.
Totally Unimodular Matrices.
Week 10.
Monday November 5th.
Totally Unimodular Matrices: Network Matrices and applications.
Wednesday November 7th.
Total Dual Integrality: Graph Orientations.
[Assignment 4 due.]
Week 11.
Monday November 12th.
Total Dual Integrality: Directed Cuts and Dijoins; Lucchesi-Younger Theorem.
[Assignment 5 assigned.]
Wednesday November 14th.
Packing Arborescences.
Week 12.
Monday November 19th.
Edge Colouring.
Wednesday November 21st.
Information Theory: Shannon Capacity.
[Assignment 5 due.]
Week 13.
Monday November 26th.
Matchings: Tutte-Berge theorem.
Wednesday November 28th.
The Primal Dual Method.
Week 14.
Monday December 3rd.
The Last Lecture.