Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Selected Topics in Combinatorial Optimization

Dr. Tobias Mömke


The book "Combinatorial Optimization" by Korte and Vygen is available electronically at Springer, if you have an MPI login. The German version is available electronically in the library.


When designing algorithms, we usually aim for algorithms with polynomial running time. Recognizing whether a problem can be solved exactly in polynomial time can be a non-trivial task. In this course you will learn about important general concepts that imply polynomial solvability. The first half of the course is dedicated to polytopes of combinatorial problems such as matchings, b-matchings, and T-joins. Afterwards the course will continue with matroids, submodular functions, and polymatroids.

Time & Date

Wednesdays, 10:00-12:00, HS001, E1 3

Exercise Class:
Thursdays 09:00–10:00 Room 415, E1 3

First lecture: Wednesday, April 16



Knowledge in linear algebra, algorithms, discrete math, complexity. The knowledge taught in the basic course "Optimization" is very helpful; if you were not able to attend the basic course previously, please consider to attend both this course and the basic course (which is also offered in summer term 2014).


Exam (written or oral, depending on the number of participants); 50% of scores from exercises are required to participate.

Number of credit points: 6


April 16, 2014 Introduction Assignment 1
April 23, 2014 Bipartite Matchings, Perfect Matching Polytope Assignment 2
April 30, 2014 Matching Polytope, Gomory Hu Trees Assignment 3
May 7, 2014 Gomory-Hu Trees, Applications of Matching Polytope Assignment 4
May 14, 2014 b-Matching Polytope Assignment 5
May 21, 2014 T-Join Polytope Assignment 6
May 28, 2014 Matroids Assignment 7
June 4, 2014 Matroid Characterizations Assignment 8
June 11, 2014 Matroid Duality, Optimization Assignment 9
June 18, 2014 Independent Set Polytope, Polyhedral Techniques Assignment 10
June 25, 2014 Matroid Intersection Assignment 11
July 2, 2014 More on Matroid Intersection/Partition Assignment 12
July 16, 2014 Greedoids, Polymatroids Assignment 13
July 17, 2014 Submodular Function Minimization
July 23, 2014 Overview of Further Results