Course NSP: Networks and Semidefinite Programming

Important information

Participants of this course: please see the lecturer's website. There you may find announcements (including deadlines), the course material, and assignments, among other information.

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.

Detailed content

• 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

Examination

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