Lecture: Approximation Algorithms - Details

Actions

• Print
• Reserve only in the timetable

Share

• Copy link to this course

Lehrveranstaltung wird online/digital abgehalten.

General information

Course number	INF-0371
Semester	WS 2020/21
Current number of participants	38
Home institute	Resource Aware Algorithmics
Courses type	Lecture in category Teaching
First date	Tue , 03.11.2020 14:15 - 15:45
Pre-requisites	Basic knowledge of Algorithms and Data Structures (e.g., Informatik III at University of Augsburg)
Online/Digitale Veranstaltung	Veranstaltung wird online/digital abgehalten.
Hauptunterrichtssprache	englisch
Literaturhinweise	David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press. Vijay V. Vazirani, Approximation Algorithms, Springer.

Lecturers

• Prof.Dr. Tobias Mömke

Course location / Course dates

n.a	Tuesday: 14:15 - 15:45, weekly

Fields of study

• Fakultät für Angewandte Informatik > Informatik

Module assignments

• Informatik M.Sc. Informatik, PO 2017, 9. > M.Sc. Informatik (PO '17), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2018, 6. > Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2018, 5. ( - WS 2020/21) > Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2017, 8. ( - WS 2020/21) > M.Sc. Informatik und Multimedia (PO '17), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2018, 5. ( - WS 2020/21) > Wahlbereich Informatik und Multimedia > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2018, 6. > Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2011, 13. > M.Sc. Informatik (PO '11), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Informationswirtschaft M.Sc. Informatik und Informationswirtschaft, PO 2011, 15. > M.Sc. Informatik und Informationswirtschaft (PO '11), Vertiefungsbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2011, 13. > M.Sc. Informatik und Multimedia (PO '11), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2018, 6. > Wahlbereich Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Mathematik Masterstudiengang Mathematik PO 2013, 11. ( - WS 2020/21) > Master Mathematik E-I: Nebenfach Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2018, 6. > Wahlbereich Informatik und Multimedia > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2017, 8. ( - WS 2020/21) > M.Sc. Informatik (PO '17), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2018, 5. ( - WS 2020/21) > Wahlbereich Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2017, 9. > M.Sc. Informatik und Multimedia (PO '17), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Informationswirtschaft M.Sc. Informatik und Informationswirtschaft, PO 2011, 14. ( - WS 2020/21) > M.Sc. Informatik und Informationswirtschaft (PO '11), Vertiefungsbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Mathematik Masterstudiengang Mathematik PO 2013, 12. > Master Mathematik E-I: Nebenfach Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik M.Sc. Informatik, PO 2011, 12. ( - WS 2020/21) > M.Sc. Informatik (PO '11), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Wirtschaftsmathematik Masterstudiengang Wirtschaftsmathematik, 12. > Modulgruppe D: Informatik [MastWiMa] > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Wirtschaftsmathematik Masterstudiengang Wirtschaftsmathematik, 11. ( - WS 2020/21) > Modulgruppe D: Informatik [MastWiMa] > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2011, 12. ( - WS 2020/21) > M.Sc. Informatik und Multimedia (PO '11), Teilbereich Informatik - Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)
• Informatik und Multimedia M.Sc. Informatik und Multimedia, PO 2018, 5. ( - WS 2020/21) > Theoretische Informatik > Approximation Algorithms, valid from WS 2020/21 > Approximation Algorithms (Vorlesung)

Comment/Description

Given an NP-hard optimization problem, how well can it be approximated in polynomial time? It is exciting and challenging to understand the approximability of fundamental optimization problems. This course mainly focuses on upper bounds, i.e., designing efficient approximation algorithms.

In this course, we will study several classes of problems, such as packing problems, network design, and graph problems. We will cover central algorithmic techniques for designing approximation algorithms, including greedy algorithms, dynamic programming, linear and semi-definite programming, and randomization.

This course does not require specific prerequisite, other than basic knowledge in algorithms and in data structures.