This course belongs to the LNMB program of PhD Courses.

** Location**

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.

** Time:**

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

** Lecturers**

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

** Examination**

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

**Rules:**

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

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