Course NSP: Networks and Semidefinite Programming

Time:	Monday 11.00 – 12.45
Period:	November 18 – December 16 2024 and January 6 2025 and January 20 – February 10 2025
Location:	All LNMB courses take place on the Campus Utrecht Science Park. Room HFG 611, Hans-Freudenthal building, Budapestlaan 6, 3584 CD Utrecht
Lecturers:	Prof. Dr. M. Laurent (CWI and Tilburg University) and Dr. S. Polak (Tilburg University)

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
CWI, P.O. Box 94079, 1090 GB Amsterdam.
E-mail: m.laurent@cwi.nl

Dr. S. Polak
Warandelaan 2,
Koopmans Building, Room K 408,
5037 AB Tilburg, Netherlands
E-mail: S.C.Polak@tilburguniversity.edu