2+1 / 5 ECTS
Many combinatorial optimization problems are known to be NP-hard, and thus are unlikely to be solvable by efficient algorithms. Unfortunately, these problems find numerous real-world applications, and thus it is crucial to find methods to solve them. One of the main approaches to circumvent the obstacle presented by NP-hardness is to settle for a less-than-optimum solution.
In this course, we will focus on approximation algorithms, which output solutions that are guaranteed to have good quality compared to the optimum solution. Throughout the semester, we will learn about the most useful and interesting techniques used in approximation algorithms, as well as the best approximation guarantees known for many classical combinatorial optimization problems.
The material for the course will be presented with weekly lectures (2h/week), and reinforced by reference chapters in well-established books, as well as exercise sets to test your knowledge and problem-solving skills. Details about the format (virtual vs presential lectures, ...) may change on short notice depending on the current situation, and will be posted on this page.
18.10.2021:The Moodle webpage is now available at: https://www.moodle.tum.de/course/view.php?id=74078.
17.10.2021:Due to COVID-19 preventive measure, the lecture tomorrow (18.10.2021) will be held on Zoom. A recording of the lecture will be posted online, and we will try to stream the lecture live to room 00.09.022. We will confirm tomorrow if this will be possible. The Zoom link and other details will be sent via e-mail to all students registered on TUMonline.
14.10.2021:Our first lecture will happen on 18.10.2021 at 12:15, in room 00.09.022 of the Math building (in Garching). Please remember to bring your COVID-19 pass and to check in using the QR code at the entrance to the room. A recording of the lecture will be posted online.
- Required: Base knowledge of linear programming, including the notions of LP duals, is necessary (e.g. Discrete Optimization [MA3502])
- Useful: Knowledge of combinatorial optimization (e.g. Combinatorial Optimization [MA4502] or Discrete Optimization [MA3502])
- Vijay V. Vazirani. Approximation Algorithms. Springer, 2001.
- David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
Online version of the books
- Vazirani: TUM Online Access
- Williamson-Shmoys: Tum Online Access, Website Version
Information about the books
- Vazirani: TUM Library
- Williamson-Shmoys: TUM Library