Course Description

Content

The task of finding an optimal solution for a given (optimization) problem is ubiquitous in computer science. A prominent example is the traveling salesman problem, where the goal is to find the shortest possible tour that visits a given set of locations. Unfortunately, for many such problems, no efficient algorithm is known that can find an optimal solution. In practice, therefore, methods are often used that may not always produce optimal solutions but instead consistently yield good ones.

In this lecture, we focus on design and analysis techniques for such algorithms. We study methods that provide a provable approximation guarantee. The term approximation guarantee refers to the ratio between the quality of an approximate solution and that of an optimal solution. For example, an algorithm with an approximation guarantee of 2 for the (metric) traveling salesman problem ensures that, for any input, it will find a tour whose length is at most twice that of the shortest possible tour (which, in general, is provably hard to compute).

Study objectives

By the end of this course, participants should be able to analyze simple approximation algorithms with respect to their approximation quality. Moreover, they should understand and be able to apply fundamental design techniques such as greedy methods, local search, scaling, and LP-based approaches.

Literature

Approximation Algorithms
Vijay V. Vazirani
Springer, 2003

The Design of Approximation Algorithms
David P. Williamson, David B. Shmoys
Cambridge University Press, 2011
Free Online-Version