Location:
Mathematical Building, Room 611AB, Budapestlaan, de Uithof, Utrecht.
Time:
Monday 10.15 - 12.00, on November 12, November 26 - December 17 & January 21 - February 4.
Course material:
The course will be based on parts of the Lecture Notes:
A Course on Combinatorial Optimization by A. Schrijver (Chapters 7,9).
Additional material which will be made available through the course (links for download will be posted below).
Examination:
Take home problems will be distributed on a weekly basis and will be posted below.
The exercises can be handed in after the end of the course.
The deadline to send the exercises is March 15, 2013.
Please mail them (pdf or ps file, no doc file) at the following address:
Monique Laurent, CWI,
Science Park 123, 1098 XG Amsterdam
or email them to: M.Laurent at cwi dot nl
Weakly assignments:
Monday November 19: No lecture.
Monday November 26:
Lecture about Chapter 7.2, 7.3, part of 7.4.
Exercises 7.12, 7.19, 7.21, 7.22.
If you are interested to read more about chordal graphs (and the related concepts of partial k-trees and tree-width of graphs) you may look at the following short surveys by Heggernes and by Bodlaender.
Exercises 7.29, 7. 32 and Exercise here.
New: Hints for Exercise 7.29 can be found here.
Monday December 10: (Change of room: room 111, Marinus Ruppertgebouw).
Lecture about Chapter 1 (Positive semidefinite matrices), Chapter 2 (Semidefinite programs), and Chapter 3.3 of the NSP Lecture Notes.
Exercises 1.1, 1.2, 1.3, and 2.1 in the NSP Lecture Notes.
Monday December 17:
Lecture about Chapters 3.4-3.7 of the NSP Lecture Notes.
Exercises 3.1, 3.2, 3.3 in the NSP Lecture Notes.
Monday January 21:
Lecture about Chapter 4.1-4.2 of the NSP Lecture Notes.
Exercises 4.1, 4.2, 4.3 in the NSP Lecture Notes.
Monday January 28:
This lecture will be given by A. Schrijver (CWI and UvA).
It will be based on Sections 9.1 and 9.2 in Chapter 9 of his Lecture Notes A Course in Combinatorial Optimization.
Exercises 9.1, 9.2, 9.3 in these lecture notes; Exercise 9.7 is facultative, but will earn you bonus points.
Monday February 4:
This lecture is based on Section 4.3 of the NSP Lecture Notes.
Exercises 4.4 and 4.5 in the NSP Lecture Notes.