Back to Ahmad's page

LTCC Combinatorial Optimisation: Packing, Partitioning, and Covering (Advanced)

Winter 2023, Block 3

Course syllabus

Announcements

Feb 6 (second update): I have also revised lectures 1 and 3. In lecture 1, there is a minor update to the statement of exercise 14b, and in lecture 3 I have replaced "weakly bipartite graph" with "weakly bipartite signed graph" in order to distinguish the notion from the one appearing in lecture 5.

Feb 6: Lecture 5 notes have been posted. Sections 1-4 were covered in class. Please read section 5 on your own. Exercises 1,2,4,6,7,8 are highly recommended.

Jan 30: Lecture 4 notes have been posted. Sections 1, 2, and the first half of 4 were covered in class. Please read the rest on your own. Exercises 3,4,6,7,11,13,15 are highly recommended.

Jan 23: Lecture 3 notes have been posted. Sections 1-4 were covered in the lecture recording. Please read sections 5 and 6 on your own. Exercises 1,2,5,7,10 are highly recommended.

Jan 16: Lecture 2 notes have been posted. I covered sections 1, 3 and 6 in class. Please read the rest on your own (section 2 may be needed for future lectures). Exercises 1,2,5,10,13 are highly recommended.

Jan 9: Lecture 1 notes have been posted. I covered sections 2 and 3 in class. Please read the rest on your own (some notions and theorem statements will be needed for future lectures). Exercises 4,5,7,13,14 are highly recommended.

Jan 6: Lecture 1 will take place on Monday, Jan 9, 13:00-15:00 at Burnside Room, De Morgan House, Russel Square.

Lecture notes:

Lecture 5 (Feb 6) Polynomial algorithms for weakly bipartite and perfect graphs.

Lecture 4 (Jan 30) Blocking and antiblocking theory.

Lecture 3 (Jan 23) Multicommodity flows and weakly bipartite signed graphs.

Lecture 2 (Jan 16) Perfect graphs.

Lecture 1 (Jan 9) Matchings.