Combinatorial Optimization 1 (MAT.321/MAT.322)

Winter Term 2020/21

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course


  On-line materials

  Exercise sheets


Under construction ....

Scheduled dates

Monday10:15-12:00SR AE06 October 4, 2021 - January , 2022
Tuesday10:15-12:00SR AE06 October 5, 2021 - January 28, 2020
Thursday16:15-18:00SR AE02 October 7, 2021 - January 29, 2020

The Monday and Tuesday slots will be devoted to the lecture part.
About every second Thursday will be devoted to the practical. The remaining Thursday slots will be used for the lecture part. Deviations from this general rule of thumb will be announced in the lecture.

Office Hours

If you happen to have questions, feel free to talk to me after the course or send me an e-mail to I'm offering virtual consultation hours via Webex or BBB if needed upon prior appointment.

Contents and Goal of the Course

The course will provide a solid introduction into the area of combinatorial optimization. The main focus will be on polynomially solvable combinatorial optimization problems (NP-hard ones are the main focus of the master course Combinatorial Optimization 2).
Note that starting from Winter Term 2014/15 the lecture part comprises 4 hours per week instead of 3 as due to a change in the mathematical programming course (Optimization 1) some material had to be moved to the Combinatorial Optimization 1 course .

I plan to cover the following topics:


The course is not based on a text book and there are no class notes available. Please take your own notes.
In the following some recommendable books are listed.

Text books and monographs

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

The two books listed below are already quite old and not up to date in all aspects, however they are classics that are recommendable in their own right.


The two following annotated bibliographies contain many further literature references for combinatorial optimization (up to at most 1997 due to their publication date):

On-Line Materials

Some further links in an wider context can be found in my mathematical programming link list Linkliste zur mathematischen Optimierung (under construction too and currently not up to date).


General comments

There will be exercise sheets which will be discussed in the practical roughly every second week on Thursdays. 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.

Not all exercises are intended to be covered in class. 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 an advanced bachelor course.

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.

If you happen to have questions to exercises not treated in class, do not hesitate to ask me for help/guidance.

Exercise Sheets

Will be made 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.)
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

The final grade will be based on the following parts:

(a) Two exams (one mid term and one near the end of the term): up to 32 points
(b) Presenting solutions to exercise problems in the practical: up to 8 points
(c) Assignment (implementation of an algorithm or preparing a summary for a paper): up to 5 points (one extra point for exceptional work)
(d) Up to 2 extra credit points for special contributions in exceptional cases

Details for (a)

There will be two exams (you need to take part in both).

For those who happen to miss one of the exams or do not end up enough points for a pass, there will be offered a single chance for a third exam (each student can choose whether he she/wants to repeat the first exam or the second exam). This extra exam will take place at the start of the next term (the date will be arranged upon mutual consent).

Details for (b)

There will be exercise sheets which will appear gradually as the semester progresses. Each announcement of a new sheet will be accompanied by a message which classifies the problem into two classes: Problems that will be handled in class and additional problems which have been added to provide you with additional material to assist your learning process and/or to help you widen and extend your knowledge beyond what is covered in the lecture.

At the beginning of each practical the students are asked to mark the problems they have prepared for with a cross. For each problem handled in class I will select one student among those who have marked the problem to present the solution on the blackboard.
It is not sufficient to have someone else solve a problem and write the solution on the blackboard without being able to explain the solution. Partial solutions will get some credit, wrong answers will get 0 points (no negative points). This should encourage students also to present solutions they are not sure about.

Details for (c)

The students can choose between two types of assignments: Implementation assignments and Paper reading assignments. Let me know your choice so that I can assihn you a project of your chosen type.

Implementation assignments/projects: You will get assigned by me one of the algorithms taught in the lecture (do not make your own choice!) and your task is to implement the algorithm. If you happen to wish another programming language than C/C++, please talk to me first.

Paper reading assignments/projects: This type of assignment is thought for all those who wish to avoid implementation work. You will get assigned by me a paper about a combinorial optimization topic (not covered in the lecture but related) and your task is to read the assigned paper and to write up a summary.

Minimal requirements for passing:
Grading key:
0 <= P < 22    Grade 5 (Nicht genügend)
22 <= P <= 28     Grade 4 (Genügend)
28 < P <= 35     Grade 3 (Befriedigend)
35 < P < =41     Grade 2 (Gut)
41 < P     Grade 1 (Sehr gut)

where P denotes the total number of points.

Last update: October 3, 2021
Bettina Klinz (