D1
Algorithms & Complexity

Approximation Algorithms

Advanced Course (2+2)

Basic Information

Lectures:Tuesdays, 10-12, Building E1 4 (MPI-INF), Room 024
Lecturer:Joachim Spoerhase
First lecture:October, 25, 2022
Tutorials:Thursdays, 14-16, Building E1 4 (MPI-INF), Room 024
Tutor:Martin Herold
First tutorial:October, 27, 2022
Credits:6 ECTS
Prerequisites:An undergraduate course in algorithms is a must. Additionally, some basic familiarity with programming (in any reasonable language) would be welcome.

Description

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.

Literature

In this lecture we use material from the following textbooks