Ahmad Abdi's webpage

Special Topics in Combinatorial Optimization: Packing and Covering

Course code: 47853-A3

Time: 10:30am-12:20pm, Tues/Thu, Jan 14 - Mar 4

Location: Tepper Quad 4219

Office hours: Thursday 2-3pm at Tepper Quad 4222

Course syllabus

Announcements:

Assignment 4 is posted.

Assignments:

Assignment 1

Assignment 2

Assignment 3

Assignment 4 (due Tuesday, Feb 26, in class or by email)

Final project (due March 8)

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