Approximation Algorithms 1+2 (Winter 2021/22)
Topical
- Logbook with detailed information about schedule and content.
- Bachelor students in PO 2019 can only get credit for part I of the course.
- Part I ends with the discussion of integrality gap in Lecture 14 on December 7.
Part II starts with the discussion of Max-Sat in Lecture 14.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Tim Koglin, Lisa Wilhelmi, Lucas Hammer (Tutor)
- LSF Entries: Part 1, Part 2, Complete course
- Lectures: Tuesday, 10:15h - 11:45h, Magnus-Hörsaal (R.M.S. 11-15) Lectures: Thursday, 10:15h - 11:45h, Hörsaal H4, Jügelhaus.
- Exercises: Friday, 14:15h - 15:45h, live via Zoom.
- Main Exam: Friday, 25.02.2022, Magnus-Hörsaal, 09:00h - 10:30h (5CP), 9:00h - 12:00h (10CP).
- Second Exam: Individual oral exams in early April
Material
Access to course material is restricted to participating students.
Lecture Notes
Last update on 10 Feb 2022 (restricted access, access information provided in the first lecture)
Most of the material is also discussed in the (German) Skript by Prof. Georg Schnitger.
Videos
Available here (access via HRZ-account)
Exercise Sheets
Weekly exercise sheets will be published here. Your solutions should be submitted as one PDF-file via moodle.
Part 1:
- Exercise Sheet 1. Issued: 26.10.2021. Due: 02.11.2021, 10:15h.
- Exercise Sheet 2. Issued: 02.11.2021. Due: 09.11.2021, 10:15h.
- Exercise Sheet 3. Issued: 09.11.2021. Due: 16.11.2021, 10:15h.
- Exercise Sheet 4. Issued: 16.11.2021. Due: 23.11.2021, 10:15h.
- Exercise Sheet 5. Issued: 23.11.2021. Due: 30.11.2021, 10:15h.
- Exercise Sheet 6. Issued: 30.11.2021. Due: 07.12.2021, 10:15h.
- Exercise Sheet 7. Issued: 07.12.2021. Due: 14.12.2021, 10:15h.
Part 2:
- Exercise Sheet 8. Issued: 14.12.2021. Due: 18.01.2022, 10:15h.
- Exercise Sheet 9. Issued: 18.01.2022. Due: 25.01.2022, 10:15h.
- Exercise Sheet 10. Issued: 25.01.2022. Due: 01.02.2022, 10:15h.
- Exercise Sheet 11. Issued: 01.02.2022. Due: 08.02.2022, 10:15h.
- Exercise Sheet 12. Issued: 08.02.2022. Due: 15.02.2022, 10:15h.
Topic
Many meaningul optimization problems are not known to allow for algorithms that always compute optimal solutions in polynomial time. An important alternative are efficient approximation algorithms that come with provable guarantees for the quality of the computed solution. The course presents such algorithms and techniques for their analysis. In particular, we focus on greedy algorithms, dynamic programming and local search. Moreover, we discuss branch-and-bound algorithms and tools from linear programming. An alternative view of the class NP via probabilistically checkable proofs is used to show the limits of efficient approximation algorithms.
Literature
- V. Vazirani. Approximation Algorithms, Springer, 2nd printing, 2003.
- D. Williamson, D. Shmoys. The Design of Approximation Algorithms, Cambridge University Press, 2011.
- D. Bertsimas, J. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific, 1997.
- C. Moore, S. Mertens. The Nature of Computation, Chapter 9, pp. 351–449, Oxford University Press, 2011.
- K. Jansen, M. Margraf. Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
- R. Wanka. Approximationsalgorithmen – Eine Einführung, Teubner, 2006.