Approximation Algorithms

Prerequisites are knowledge of algorithms and data structures, basic graph problems and graph algorithms (e.g., as provided in the lecture "Netzwerkalgorithmen"); basic knowledge from theoretical computer science (NP-completeness) is helpful.

Many interesting and natural algorithmic problems (e.g., the Traveling Salesman Problem) are NP-complete - hence, we cannot expect to find a "perfect" algorithm that (i) always and (ii) fast finds (iii) an optimal solution. However, hard problems still need to be solved!

In this class we consider algorithms that do not necessarily find an optimal solution, but that (i) always and (ii) fast find a (iii) provably good solution.

Among the topics of this class are:

1. A basic introduction to NP-completeness and approximation
2. Approximation for vertex and set cover
3. Packing problems
4. Tour problems and variations
5. Current research problems

In the context of various problems, a wide spectrum of techniques and concepts will be provided.

Organization

If you run into any problems, please contact Peter.

• There is a mailing list for this class. Please sign up, as we will use it for communication. This list is moderated which may cause a slight delay upon registration.
• We only use this website and the mailinglist to distribute information; the information on other sites such as StudIP etc. may be missing or outdated.
• You can find additional course material on the material page.

Homework

Literature

The first part of the lecture will be on classic results for which the following books can be useful.

• Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001 [PDF].
• Approximation Algorithms for NP-hard problems edited by Dorit S. Hochbaum, more info.
• The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, published by Cambridge University Press (online). more info

The second part of the lecture will be on recent results for which the corresponding papers will be announced in due time.