Course NSP: Networks and Semidefinite Programming

Time:	Monday 11.00 – 12.45
Period:	November 21 - December 19 (2022) and January 30 - February 27 (2023)
Location varies per week:	All LNMB courses are on the Campus Utrecht Science Park: January 30 : Buys Ballot building, room 061 February 6 : Buys Ballot building, room 023 February 13 : Minaert building, room 2.01 February 20 : Buys Ballot building, room 161 February 27 : Buys Ballot building, room 023 Details about online facilities for students follow upon registration.
Lecturers:	Prof.dr. M. Laurent (CWI and Tilburg University) and dr. S. Polak (CWI).

Course description:
Combinatorial optimization problems are concerned with the efficient allocation of limited resources to meet desired objectives when the values of the variables are restricted to be integral. Such problems arise in various applications, e.g., airline crew scheduling, manufacturing, network design, cellular telephone frequency design, and they can often be modeled as optimization problems on graphs. The course deals with several basic combinatorial optimization problems. While these problems are intrinsically hard to solve in general, we will present polynomial-time solvable instances. Algorithms use combinatorial tools, linear and semidefinite programming.

The following subjects are discussed:
- problems, algorithms and running time; basics of semidefinite programming;
- cliques, cocliques and colouring in graphs; Lovász theta number;
- maximum cuts in graphs; Goemans and Williamson approximation algorithm.

Literature:
- Lecture notes: A Course in Combinatorial Optimization, A. Schrijver, CWI (chapters 6,7,9).
- Additional lecture notes on chosen topics will be provided.
- A. Schrijver, Combinatorial Optimization: Polyhedra and efficiency, Volumes A, B, and C, Springer 2003.

Prerequisites:
Basic knowledge of linear algebra, graph theory and linear programming. (Bachelor level courses.)

Examination:
Take home problems.

Address of the lecturers:
Prof.dr. M. Laurent and dr. S. Polak
CWI, P.O. Box 94079, 1090 GB Amsterdam.
E-mail: m.laurent@cwi.nl and sven.polak@cwi.nl