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

Winter Term 2019/20

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course


  On-line materials

  Exercise sheets


Scheduled dates

Monday10:15-12:00SR AE06 October 7, 2019 - January 27, 2020
Tuesday16:15-18:00SR AE06 October 1, 2019 - January 28, 2020
Wednesday14:15-16:00SR AE06 October 2, 2019 - January 29, 2020

The Monday and Tuesday slots will be devoted to the lecture part.
About every second Wednesday 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

To accomodate for the needs of diverse groups of students as good as possible, I do not have a fixed consulation hour. If you happen to have questions, feel free to talk to me after the course, send me an e-mail to, or just drop into my office if you can live with the risk that I'm not there or have no time. For more time-consuming matters I recommend that you make an appointment with me in advance.

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

  • Exercise Sheet 1    PostScript file    Adobe pdf file    (Pages 1-4, Problems 1-23)
    (Issued on October 9, 2019, treated in class on October 16, 2019 and October 31, 2019.)

  • Exercise Sheet 2    PostScript file    Adobe pdf file    (Pages 5-8, Problems 24-48)
    (Issued on October 24, 2019, treated in class on October 31, 2019 and November 13, 2019.)

  • 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: November 4, 2019
    Bettina Klinz (