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

Summer Term 2018

Bettina Klinz

  Scheduled dates

  Office hours

  Contents of the course


  Exercise sheets


Scheduled dates

Monday16:15-18:00SR AE06 March 5, 2017 - June 25, 2018
Wednesday14:15-16:00SR AE06 March 9, 2017 - June 27, 2018

About every second Wedesday will be devoted to the practical (exceptions can occur). The remaining slots will be used for the lecture part.

Office Hours

To accomodate for the needs of diverse groups of students as well 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 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 and there are no class notes available. Please take your own notes.
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.


General comments

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

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-27)
    (Issued on March 8, 2018, treated in class on March 21, 2018 and April , 2018)

  • Exercise Sheet 2    PostScript file    Adobe pdf file    (Pages 5-8, Problems 28-60)
    (Issued on April 25, 2018, treated in class on May 2, 2018 and May 28, 2018)

  • Exercise Sheet 3    PostScript file    Adobe pdf file    (Pages 9-12, Problems 61-88)
    (Issued on May 22, 2018, treated in class on May 28, 2018 and June , 2018)

  • 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) A written exam (at the end of the term): up to 24 points
    (b) Presenting solutions to exercise problems in the practical: up to 10 points
    (c) Assignment (implementation of an algorithm or preparing a summary for a paper): up to 5 points for the normal version and up to 8 points for exceptional cases which go well beyond the normal version (depends on both the nature of the project and what's handed in how many points are achievable)
    (d) Up to 2 extra credit points for special contributions in exceptional cases

    Details for (a)

    The date for the exam will be fixed together with the students.

    For those who happen to miss the exam or do not end up enough points for a pass, there will be offered a single chance for a 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 on the basis level: Implementation assignments and Paper reading assignments. Let me know your choice so that I can assign 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.

    For those with a special interest into the area, there is also the option to get assigned a project on the extended level which needs more time and might e.g. involve reading several papers, trying to extend something known in the literature etc.

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

    where P denotes the total number of points.

    Last update: May 23, 2018
    Bettina Klinz (