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.