WS25: Approximation Algorithms
Avsnittsöversikt
-
Scope: 5 ECTS, 2+2 SWS Time and Place: Lecture: Friday, 10:15–11:45, M2, ÜR I (first lecture on Oct. 17)
Tutorial: Tuesday, 10:15–11:45 Uhr, M2, SE I (first tutorial on Oct. 21)Oral exam: Tuesday, February 17, 2026 Target Group: Master Computer Science, Master Mathematics, Master Computational Mathematics Lecture: Prof. Alexander Wolff Tutorials: Antonio Lauerbach -
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, 2003The Design of Approximation Algorithms
David P. Williamson, David B. Shmoys
Cambridge University Press, 2011
Free Online-Version -
- In the table below, if you click on the date, you get the printer version of the slides; if you click on the topic of a lecture, you get the long version of the slides.
- The videos were made by Joachim Spoerhase during covid years. Enjoy!
Date Topic Videos (old!) Literature 17.10.2025 Introduction and Vertex Cover (25.10.25: added half-integrality) Lecture 01 [Vazirani, Chapter 1] 24.10.2025 Set Cover and Shortest Superstring Lecture 02 [Vazirani, Chapter 2] 31.10.2025 Steiner Tree, approximation-preserving reduction, Multiway Cut Lecture 03 [Vazirani, Chapters 3+4] 07.11.2025 Linear programming and LP-duality Lecture 04 [Vazirani, Chapter 12] 14.11.2025 LP-based methods for Set Cover Lecture 05 [Vazirani, Chapters 14+15] 21.11.2025 Metric k-Center via parametric pruning Lecture 06 [Vazirani, Chapter 5] 28.11.2025 Scheduling via parametric pruning Lecture 07 [Vazirani, Chapter 17] -