Ahmad Abdi's webpage

Special Topics in Combinatorial Optimization: Packing and Covering

Course code: 47853-A3

Course syllabus

Course notes (without citations)


The course is finished. I have uploaded the course notes. We did not have time to cover chapters 10 and 11.

I have summarized some of the open questions and conjectures in the field here.


Assignment 1

Assignment 2

Assignment 3

Assignment 4

Final project

Lecture notes:

Lecture 1 (Jan 15): Menger's theorem, Dilworth's theorem

Lecture 2 (Jan 17): integral polyhedra, TDI linear systems, packing and covering models, balanced matrices

Lecture 3 (Jan 22): characterization of balanced matrices, coloring balanced matrices and hypergraphs, integral polyhedra associated with balanced matrices

Lecture 4 (Jan 24): Hall's theorem for balanced hypergrpahs, perfect graphs

Lecture 5 (Jan 29): the max-max inequality, the weak perfect graph theorem, the star cutset lemma, substitution and duplication

Lecture 6 (Feb 5): the antitwin lemma, the strong perfect graph theorem, TDI systems associated with perfect graphs

Lecture 7 (Feb 7): perfect matrices, the pluperfect graph theorem, antiblocking theory, clutters

Lecture 8 (Feb 12): blockers, ideal and Mengerian clutters, the width-length inequality, minor operations

Lecture 9 (Feb 14): the Lucchesi-Younger theorem, Woodall's conjecture

Lecture 10 (Feb 19): T-joins and T-cuts, packing T-cuts in bipartite graphs

Lecture 11 (Feb 21): the Edmonds-Johnson theorem, the four color theorem, minimally nonideal clutters, the deltas

Lecture 12 (Feb 26): finding delta minors, finding odd hole minors, cross regular matrices

Lecture 13 (Feb 28): Lehman's characterizations of minimally nonideal clutters, consequences