Back to Ahmad's page

LTCC Combinatrial Optimisation: Packing, Partitioning, and Covering

Winter 2021, Block 4

Course syllabus

Final Exam

Lecture notes

    Lecture 5 (Mar 15) Set Packing Programs. Antiblocking Polytopes. Perfect Matrices. Equivalence of Perfect Matrices and Perfect Graphs. Exercises.

    Lecture 4 (Mar 8) Set Covering Programs. Blocking Polyhedra. Clutters. Width-Length Inequality. Exercises.

    Lecture 3 (Mar 1) Menger's Theorem. Multicommodity Flows and The Cut Condition. Signed Graphs and Weakly Bipartite Graphs. Planar Graphs. Exercises.

    Lecture 2 (Feb 22) Perfect graphs. Dilworth's Theorem. Perfect Graph Theorem. Meyniel Graphs. Cographs. Chordal Graphs. Exercises.

    Lecture 1 (Feb 15) Konig's and Hall's Theorems. Tutte-Berge Formula. Edmonds' Blossom Algorithm. Edmonds-Johnson Theorem. Exercises.