Digicampus
Vorlesung: Approximation Algorithms - Details
Sie sind nicht in Stud.IP angemeldet.
Lehrveranstaltung wird online/digital abgehalten.

Allgemeine Informationen

Veranstaltungsname Vorlesung: Approximation Algorithms
Veranstaltungsnummer INF-0371
Semester WS 2020/21
Aktuelle Anzahl der Teilnehmenden 26
Heimat-Einrichtung Resource Aware Algorithmics
Veranstaltungstyp Vorlesung in der Kategorie Lehre
Erster Termin Dienstag, 03.11.2020 14:15 - 15:45
Voraussetzungen 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.

Räume und Zeiten

Keine Raumangabe
Dienstag: 14:15 - 15:45, wöchentlich

Kommentar/Beschreibung

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.