Research Institute for Discrete Mathematics

Lecture Course "Combinatorial Optimization"

Winter Term 2011/12

This is the introductory module in area C (Discrete Mathematics) of the Master's Programme in Mathematics and an introductory module in the area "Algorithmics" of the Master's Programme in Computer Science. This course should be attended by beginning master's students (unless they focus on other areas). Basic knowledge in combinatorial algorithms, in particular network flows, is required.

This course covers the following topics: connectivity in graphs, Gomory-Hu trees, nonbipartite matching, Edmonds' weighted matching algorithm, generalized matching problems, T-joins and T-cuts, submodular functions, network design, traveling salesman problem, polyhedral combinatorics. Some additional topics may be covered as well, including very recent results.

This course is in English. Most of it will be based on the following book:

B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Fourth edition 2008

Another very recommendable (and very comprehensive) book covering many (but not all) of the topics is:

A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer 2003

Both books (and many others) are available in our library.

Class Hours: Tuesdays and Thursdays 2-4 pm (14:15-15:45)
Room: Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
Exercise Classes: By appointment.

Jun.Prof. Dr. T. Nieberg

Class Hours:	Tuesdays and Thursdays 2-4 pm (14:15-15:45)
Room:	Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2)
Exercise Classes:	By appointment.