LNMB PhD Course Networks and Semidefinite Programming - Fall 2014

This course belongs to the LNMB program of PhD Courses.

Mathematical Building, Room 611AB, Budapestlaan, de Uithof, Utrecht.

Monday 10.15 - 12.00, November 12-December 15 and January 19-February 9.

Course material:
The course will be based on parts of the Lecture Notes: A Course on Combinatorial Optimization by A. Schrijver (abbreviated below as [LNAS]).
Additional material which will be made available through the course (links for download will be posted below).

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 April 1.

Please mail a print or email them (pdf file, no doc file) at the following address:
Monique Laurent, CWI, Science Park 123, 1098 XG Amsterdam
M.Laurent at cwi dot nl

Weakly assignments:

Monday November 17:

Lecture about Chapter 6 and Chapter 7.1 in [LNAS].
The exercises can be found here.

Monday November 24:

Lecture about Chapters 7.2, 7.3 and part of 7.4 in [LNAS].
Exercises 7.12, 7.19, 7.21, 7.22.

Monday December 1:

Lecture about Chapters 7.4 and 7.5 in [LNAS].
Before the next lecture please read Chapter 1 in these SDO Lecture Notes, abbreviated below as [SDO].
Exercises 7.29 and 7.32 in [LNAS] and Exercises 1.1 and 1.2 in [SDO].
Hints for Exercise 7.29 can be found here.

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.

Monday December 8:

Lecture about Chapter 2.1 and Chapter 3.2. Please read also Chapters 2.2 and 2.3.
Exercices 2.1, 2.2, 2.3, 2.4 in [SDO].

Monday December 15:

Lecture about Chapters 3.3, 3.4, 3.5. Please read also Chapter 3.7.
Exercises 3.1, 3.2, 3.3 in [SDO].

Monday January 19:

Lecture about Chapters 3.6, 3.8 and part of 4.1. [Small updates have been made in these chapters in the SDO Lecture Notes].
Exercises 3.4, 3.5 and 4.2 in [SDO].

Monday January 26:

Lecture about Chapter 4.1-4.2 (small updates made in [SDO]).

Exercises 4.3, 4.4, 4.5, 4.6 in [SDO].

Monday February 2:

Unfortunately this lecture is cancelled (as there are no trains to/from Utrecht).

Monday February 9:

Lecture about Sections 4.3 and 4.4 (small updates made in these sections in [SDO]).
Exercises 4.7 and 4.8 in [SDO].