Courses > PHD Courses
Top image

Management Team
Dutch OR Groups

Landelijk Netwerk Mathematische Besliskunde

Course NSP: Networks and Semidefinite Programming 

Time: Monday 13.00 – 14.45 (September 7 - November 9).
Location: All LNMB courses will be taught on-line until further notice. Upon registration, students receive a link for the video connection.
Lecturer: Prof.dr. M. Laurent (CWI and Tilburg University).

Course description:
(for participants of this course: see the lecturer's website)

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;
- cuts and metrics; multicommodity flows and disjoint paths.

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

Basic knowledge of linear algebra, graph theory and linear programming.

Take home problems.

Address of the lecturer:
Prof.dr. M. Laurent
CWI, P.O. Box 94079, 1090 GB Amsterdam.
Phone: 020 - 5924105.