186.102 Approximation Algorithms
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019W, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

- den Unterschied zwischen exakten und approximativen Lösungen zu erläutern
- eigenständig die Approximationsgüte von Algorithmen zu analysieren
- klassische Approximationsresultate für diskrete Optimierungsprobleme zu reproduzieren
- Publikationen über Approximationsalgorithmen zu verstehen

 

Inhalt der Lehrveranstaltung

- Qualitätsmaße von Approximationsalgorithmen
- Schemata von Heuristiken und Methoden der Approximationsabschätzung
- Heuristiken und ihre Analyse für Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover und Set Cover Probleme

Methoden

Diskussion von Fallbeispielen, Lösen von Übungsbeispielen und Präsentation in der Vorlesung

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

ECTS-Breakdown:

21h   Vorlesung
20h   Vorbereitung der Übungsbeispiele
  6h   Präsentation der Übungsbeispiele
25h   Prüfungsvorbereitung
  3h   Prüfung
-----
75h   total 


Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.16:00 - 19:0002.12.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.13:00 - 16:0003.12.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mo.17:00 - 20:0016.12.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Di.13:00 - 16:0017.12.2019Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
Mi.13:00 - 16:0008.01.2020Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Do.13:00 - 16:0009.01.2020Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.13:00 - 16:0010.01.2020Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Mo.17:00 - 20:0020.01.2020Seminarraum FAV EG C (Seminarraum Gödel) Vorlesung
LVA wird geblockt abgehalten

Leistungsnachweis

After a successful completion of the course, students are able to understand the complexity respectively the approximability status of discrete optimization problems. Moreover, they have the theoretical basics for doing a worst-case analysis for a given approximation algorithm.

LVA-Anmeldung

Von Bis Abmeldung bis
07.10.2019 00:00 22.10.2019 23:59

Curricula

Literatur

K.  Jansen, M.  Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.

R. Wanka, Approximationsalgorithmen: Eine Einführung, Teubner, 2006.

D.S. Hochbaum,  Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997.

V.V. Vazirani,  Approximation Algorithms,  Springer, 2001.

G. Ausiello et al., Complexity & Approximation, Springer, 1999.

Vorkenntnisse

Kenntnisse über grundlegende Algorithmen und Datenstrukturen, einfache Beweistechniken

Begleitende Lehrveranstaltungen

Sprache

Deutsch