Combinatorial Optimization 2 (MAT.482/MAT.483)

Summer Term 2021

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course


  Exercise sheets


Scheduled dates

Due to COVID19 the course this term is held in an online manner. For details see the TC course. The lectures are recorded and you can watch the videos at your favourite time. There will be online meetings for the practical. Information will be sent to the registered students via TUG-Online.

Office Hours

This term there are no regular office hours. If you happen to have questions, feel free to send me an e-mail to I can also answer questions in the forum of the TC course or offer a chat session if there is a demand.

Contents and Goal of the Course

The course builds on the Combinatorial Optimization 1 course which mainly focused on polynomially solvable combinatorial optimization problems (minimum spanning tree, branchings, shortest path, maximum flow, minimum cost flow, cardinatity matching, total unimodularity).
The Combinatorial Optimization 2 course is an extension of the Combinatorial Optimization 1 course and deals with important combinatorial optimization problems which are not covered in the Combinatorial Optimization 1 course with a particular focus on NP-hard combinatorial optimization problems. The goal of the course is not only to deal with additional classes of combinatorial optimization problems, but also provide the students with an arsenal of diverse approaches to attack hard combinatorial optimization problems (exact approaches, heuristics, approximation algorithms, special cases).

I plan to cover the following topics:


The course is not based on a text book.
In the following some recommendable books are listed.

General text books and monographs

The following four books provide a good overview about the area of combinatorial optimization.

Literature about special topics (QAP, TSP, approximation)

For further literature links, see the course page of my course Combinatorial Optimization 1 and the TC course.


General comments

There will be exercise sheets made available. Students should try to solve the exercises on their own. The exercises should help to obtain a better understanding of the material taught in the lecture part.

I added a number of additional exercise to point out connections to topics related to those treated in class and to encourage the students to extend their level of understanding of combinatorial optimization and to get acquainted with problem solving on a level adequate for a course at master level.

The degree of difficulty of the problems varies. Some are very basic, others are of average difficulty and some are actually quite challenging at this level. Feel free to as for guidance for the more challenging ones.

Exercise Sheets

None yet available

Exam/Grading information

Grading of the Lecture

There will be an oral exam for the lecture. (Special arrangements possible for those who do not take part in this year's practical.) The exams at the end of the term will be held in an online manner (be prepared that you either need a tablet or the possibility to film what you write on a sheet of paper).
I will not register the oral exams in TUG-Online in advance. Please make your own appointment with me (best at least a few days before you want to get examined).

When preparing for the exam, aim at understanding the material presented in the lecture. It is not sufficient to learn algorithms and proofs by heart.

Grading of the Practical

Due to COVID19 there will be a specially adapted grading scheme. Details will be discussed in the initial meeting.

Last update: March 3, 2021
Bettina Klinz (