Skip to main content

MA252 Schedule

All references below are to sections of A Course in Combinatorial Optimization by A. Schrijver, unless otherwise stated.

Week 1 (Jan 7-11): Introduction, Paths and Trees

  • Lecture 1: Introduction to combinatorial optimisation, graphs, directed graphs and linear programs. Lecture Notes 
  • Lecture 2: Shortest paths, Dijkstra's algorithm. Sections: 1.1, 1.2. See also Section 1.8 of Bondy and Murty.
  • Lecture 3: Minimum spanning trees, Dijkstra-Prim Algorithm, Kruskal's Algorithm. Section: 1.4. See also Section 2.5 in Bondy and Murty.

Week 1 Exercises

Week 2 (Jan 14-18): Linear Programming

  • Lecture 1: Basics of linear programs, setting up linear programs, polyhedra and polytopes. Sections 2.1, 2.2, 2.4. See also Goemans's notes here and here.
  • Lecture 2: Farkas' Lemma, separating hyperplane theorem. Sections 2.1-2.3. See also Williamsons's notes here and here and Goemans's notes here.
  • Lecture 3: Farkas' Lemma continued, linear programming duality. Section: 2.4. See also Goemans's notes here.

Week 2 Exercises

Week 3 (Jan 21-25): Matchings in Bipartite Graphs

  • Lecture 1: Bipartite graphs, matchings, covers, Gallai's Theorem, Sections: 3.1, 3.2. See also Sections 5.1 of Bondy and Murty.
  • Lecture 2: KÅ‘nig's Theorem, Hall's Marriage Theorem, bipartite matching algorithms. Sections: 3.3, 3.4. See also Sections 5.2, 5.4 and 5.5 of Bondy and Murty.
  • Lecture 3: The matching polytope. Section: 3.5.

Week 3 Exercises

Week 4 (Jan 28-Feb 1): Flow Problems

  • Lecture 1: Menger's Theorem. Section: 4.1. See also Section 11.4 of Bondy and Murty.
  • Lecture 2: Max-Flow Min-Cut. Section: 4.2. See also Sections 11.1, 11.2 and 11.3 of Bondy and Murty.
  • Lecture 3: Ford-Fulkerson Algorithm. Section: 4.3.

Week 4 Exercises

Week 5 (Feb 4-8): Non-Bipartite Matching

  • Lecture 1: Tutte's Theorem, Tutte-Berge Formula. Section: 5.1. See also Section 5.3 of Bondy and Murty.
  • Lecture 2: Matching algorithms. Sections: 5.2, 5.3.
  • Lecture 3: Return of the matching polytope. Section: 5.4.

Week 5 Exercises

Week 6 (Feb 11-15): Complexity Theory

  • Lecture 1: Algorithms, problems, running time. Sections: 6.1, 6.2, 6.3, 6.4.
  • Lecture 2: NP, co-NP and completeness. Sections: 6.5, 6.6, 6.7
  • Lecture 3: Proving NP-completeness. Sections: 6.8, 6.9.

Week 6 Exercises

Week 7 (Feb 18-22): Cliques, stable sets and colourings

  • Lecture 1: Cliques and vertex colourings. Section: 7.1.
  • Lecture 2: Edge colourings. Section: 7.2.
  • Lecture 3: Perfect and chordal graphs. Sections: 7.4, 7.5.

Week 7 Exercises

Week 8 (Feb 25-March 1): Treewidth and Dynamic Programming

  • Lecture 1: Tree decompositions, brambles and separators. Notes1 Survey Paper
  • Lecture 2: Tree decompositions, brambles and separators (continued).
  • Lecture 3: Dynamic programming on graphs of bounded tree-width.

Week 8 Exercises

Week 9 (March 4-8): Multicommodity Flows

  • Lecture 1: Introduction, two-commodity case. Sections: 9.1, 9.2.
  • Lecture 2: Acyclic directed graphs. Section: 9.3.
  • Lecture 3: On planar graphs. Section: 9.4.

Week 10 (March 11-15): Matroids

  • Lecture 1: Introduction, greedy algorithms, equivalent axioms. Sections: 10.1, 10.2.
  • Lecture 2: Examples of matroids, technical lemmas. Sections: 10.3, 10.4.
  • Lecture 3: Edmonds' Matroid Intersection Theorem. Section: 10.5.

Week 10 Exercises

1Permission to use these notes was generously given by the author, J. Erickson.