Research Institute for Discrete Mathematics

Lecture Course "Combinatorial Optimization"

Winter 2008/09


This is a basic course in the area C (Discrete Mathematics) of the Master's Program in Mathematics and should be attended by beginning master students. Basic knowledge in combinatorial algorithms, in particular network flows, is required, as provided e.g. in the bachelor module "Einführung in die Diskrete Mathematik".

The course can be also taken by students in the (expiring) Diploma Program who have already attended some basic courses in "Diskrete Mathematik".

The course will cover the following topics:
Matchings, b-Matchings, generalized matching problems, T-joints and T-cuts, disjoint paths, submodular functions, optimization over matroids, polyhedral combinatorics, NP-hard problems.

Since it is part of the Master's Program, the course will be given in English. Most of it will be based on the following book:


Class Hours: Tuesdays and Thursdays 2-4 pm (14:15-15:45)
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
First Class: October 14, 2008
Exercise Classes: See website of exercises


Priv.-Doz. Dr. C. Buchheim