Allgemeine Informationen
| Veranstaltungsname | Kurs: 03-IMAT-APX Approximation Algorithms |
| Untertitel | |
| Veranstaltungsnummer | 03-IMAT-APX |
| Semester | SoSe 2025 |
| Aktuelle Anzahl der Teilnehmenden | 34 |
| Heimat-Einrichtung | Informatik |
| Veranstaltungstyp | Kurs in der Kategorie Lehre |
| Erster Termin | Donnerstag, 10.04.2025 14:00 - 16:00, Ort: MZH 1450 |
| Art/Form | |
| Leistungsnachweis | Oral exam |
| Englischsprachige Veranstaltung | Ja |
| Sonstiges |
This course deals with the design and analysis of algorithms for combinatorial optimization problems such as they arise in communication, project planning, and logistics. These problems are typically computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide any hard guarantees on the performance in comparison to the optimum solution. In this course, we study polynomial-time algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on the worst-case performance. Topics include: - Greedy algorithms and Local Search - Rounding Data and Dynamic Programming - Deterministic Rounding of Linear Programs (LPs) - Random Sampling and Randomized Rounding of LPs - Primal-Dual Methods - Hardness of Approximation - Problem Solving under Uncertainty Format and Examination We will teach the course with 4 hours per week (6 ECTS), where roughly every other week one class will be an interactive exercise session. There is the possibility to further extend the content of the course as well as the credits by participating in a seminar. This participation consists of individually studying a recent research article and presenting the main results to the rest of the class. |
| ECTS-Punkte | 6 |
