Location:
Hans Freudenthal Gebouw (Mathematical Building), Room 611AB, Budapestlaan, de Uithof, Utrecht.

Time:
Monday 11.00 - 12.45, November 21-December 19 and January 23-February 20.

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).

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 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:

Lecture about Chapter 6 and (part of) Chapter 7.1 in [LNAS].
The exercises can be found here. We will discuss the Strong Perfect Graph Theorem next week as well as the notion of graph minors, so you may want to postpone working on Exercises 3, 4 till next week.
In part 2) of Exercise 4 one needs to assume that the graph G is 2-connected, which means that G is connected and does not admit a cutset of cardinality one.

Monday November 28:

Lecture about Chapters 7.1, 7.2, 7.3 in [LNAS]. We will finish the discussion about Dilworth's theorem next week.
Exercises 7.9(ii), 7.12, 7.19, 7.21, 7.22.

Monday December 5:

Lecture about Chapters 7.3 (Dilworth theorem), 7.4 and 7.5 in [LNAS]. We will finish the discussion about tree representations of chordal graphs next week.
Exercise 7.32 and the two exercises here.

Monday December 12:

Lecture about Chapter 7.5 in [LNAS] and Chapter 3.2 in the SDO Lecture Notes, abbreviated below as [SDO].
Please read Chapter 1 of [SDO] before the next lecture.
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 survey by Heggernes.

Exercises 1.1 and 1.2 in [SDO] and the following two exercises:

Exercise A: Assume that G1 and G2 are two perfect graphs, with disjoint sets of vertices. Build the new graph G, obtained by taking the union of G1 and G2, and adding all possible edges between nodes of G1 and nodes of G2. Show that G is perfect.

Exercise B: Give a class of perfect graphs having exponentially many maximal stable sets and exponentially many maximal cliques (in terms of the number of nodes).

Monday December 19:

Lecture about Chapters 1 and 2 in [SDO].
Exercises 2.1, 2.3, 2.4 in [SDO] and this Exercise C.
Correcting typos: The additionnal exercise should have been named Exercise C (instead of Exercise A), and more importantly in equation (1) the condition on the trace should read Tr(X)=k (instead of Tr(X)=1).

Monday January 23:

No class on Monday 23, 2017.

Monday January 30:

Lecture about Chapter 3.3 and 3.4 in [SDO] (computing maximum stable sets and minimum colorings in perfect graphs, and equivalent formulations for the theta number).
Exercises 3.1, 3.2, 3.3 in [SDO].

Monday February 6:

Lecture about Chapter 3.6 (theta bound for vertex-transitive graphs), Chapter 3.7 (bounding the Shannon capacity) and Chapter 3.8 (bounding a geometric parameter).
Exercises here.

Monday February 13:

Lecture about Sections 4.1 and 4.2 (Max-Cut and Goemans-Williamson approximation algorithm).
Exercises 4.1, 4.5 and 4.6 in [SDO].

Monday February 20:

Lecture about Sections 4.3 and 4.4 (extension of the Goemans-Williamson approach to other problems: max bisection, max k-cut, max 2-SAT, some quadratic integer problems).
For max k-cut I omitted to mention in class that one needs to use a modified SDP, please check the Lecture Notes.

Exercise 4.7 in [SDO].