Approximation Algorithms

Advanced Course (2+2)

Basic Information

Lectures:Tuesdays, 10:15-11:45, Building E1 4 (MPI-INF), Room 024 and via zoom
Lecturer:Joachim Spoerhase
First lecture:October, 25, 2022
Tutorials:Thursdays, 14-16, Building E1 4 (MPI-INF), Room 024 and via zoom
Tutor:Martin Herold
First tutorial:October, 27, 2022
Credits:6 ECTS
Prerequisites:An undergraduate course in algorithms (eg, big-Oh notation) is a must. Basic knowledge in theoretical computer science (eg, NP-hardness) and knowledge of basic terminology in graphs is recommended but not necessary.
Lecture Materials:We will provide the materials (slides, exercise sheets, and zoom link) via moodle . For subcription to the moodle course a password is needed. We will provide the password in the first lecture. If you are planning to attend the first lecture virtually please send an e-mail to Martin Herold (mherold (at) mpi-inf (dot) mpg (dot) de).


The task of determining an optimal solution for a given problem (discrete optimization problem) is ubiquitous in computer science. A prominent example is the Travelling Salesman Problem where the goal is to find a shortest tour that visits a given set of locations. Unfortunately, for many optimization problems, no efficient algorithms are known (and under standard complexity theoretic assumptions, no such algorithms are expected to exist). However, feasible solutions are still required in practice. Thus, one approach is to determine efficient algorithms that provide provably good (but not necessarily optimal) solutions. In this lecture we discuss the design and analysis of techniques for such algorithms. Namely, we consider methods that provide a guaranteed approximation ratio (i.e., a bounded ratio between the objective value of a computed solution and the objective value of an optimal solution). For example, we will see an algorithm for the Travelling Salesman Problem where the ratio between the tour provided by the algorithm is at most two times the value of a shortest tour.

Learning Objectives

By the end of this course participants should be able to analyze simple approximation algorithms with respect to their quality. They should also be able to apply basic design techniques (e.g., greedy, local search, scaling, and LP-based methods) to approximately solve discrete optimization problems.


In this lecture we use material from the following textbooks