Approximation Algorithms

Advanced Course in Summer 2018

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.


Dr. Ruben Hoeksma (Email)
Prof. Dr. Nicole Megow (Email)
Time & Room:

Mon 14-16 in room MZH 1090
Thu 10-12 Uhr in room MZH 1110
Thursday, April 5, 2018
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
  • The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
  • Approximation Algorithms, Vijay V. Vazirani online version