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.

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

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

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 Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Fr.15:00 - 18:0008.10.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
15:00 - 18:0014.10.2021 - 15.10.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Do.15:00 - 18:0021.10.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.15:00 - 18:0005.11.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
15:00 - 18:0018.11.2021 - 19.11.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.15:00 - 18:0003.12.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.15:00 - 18:0014.01.2022Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Approximation Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Fr.08.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Do.14.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.15.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Do.21.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.05.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Do.18.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.19.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.03.12.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fr.14.01.202215:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) 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
27.09.2021 00:00 05.10.2021 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