LNMB PhD Course Networks and Semidefinite Programming - 2nd Trimester in 2022-2023

This course belongs to the LNMB program of PhD Courses.

This course is given onsite at Utrecht Campus Science Park. The lectures will also be streamed and be accessible online. Details about the lecture rooms and online facilities are sent via LNMB after registration to the course.

Monday 11.00 - 12.45, November 21 - December 19 2022 and January 30 - February 27 2023.

Monique Laurent (CWI, Tilburg University), Sven Polak (CWI)

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]), and on the Lecture Notes: Networks and Semidefinite Programming (abbreviated below as [NSP]).

Take home problems will be distributed on a weekly basis and will be posted below.

- You may work in group of two students and return a common solution set for the group (but every student is expected to work individually on all exercises).
- Write the solutions preferably in Latex. Handwritten solutions must be written in a careful and well readable manner.
- The solutions can be handed in after the end of the course.
- Please mail a print or email them (pdf file, no doc file) at the following address:
Sven Polak, CWI Science Park 123, 1098 XG Amsterdam, Sven.Polak@cwi.nl (with cc to M.Laurent@cwi.nl)
- The deadline to send the solutions is March 17 2023.

Program of the course and weekly assignments:

Monday 21 November [only onsite, not streamed]
Room 061 in Buys Ballot building.

Lecture about part of Chapter 6 and Chapter 7.1 in [LNAS]: basic facts about complexity classes, introducing basic graph parameters (stable sets, cliques, coloring) and some facts on their complexity.

Homework Exercises: Exercise 7.6 in [LNAS], Exercises A & B as posted at the shared surfdrive folder. (You may want to work on Exercise B after the next lecture.)

Monday 28 November
Room 061 in Buys Ballot building.

Lecture about Chapters 7.1 and 7.2 in [LNAS]: vertex and edge covers, vertex and edge coloring of graphs.

Homework Exercises: posted at the shared surfdrive folder.

Monday 5 December

Monday 12 December

Monday 19 December [only onsite, not streamed]

Monday 30 January

Monday 6 February

Monday 13 February

Monday 20 February [only onsite, not streamed]

Monday 27 February

Reserve slot (in case one other lecture would need to be canceled).