Modulcode:	MS0201
Englische Bezeichnung:	Approximation Algorithms
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS08/09 WS10/11 SS12 WS14/15 WS15/16 WS16/17 WS17/18 SS19 SS20 SS21 WS22/23 WS24/25)
Präsenzzeiten:	2V 2Ü 2S
ECTS:	8
Workload:	30 Std. Vorlesung, 30 Std. Readingseminar 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) AM-IDWM (MSc WInf) OR (MSc WInf) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS

Kurzfassung:

In diesem Modul werden neue Techniken des Entwurfes und der Analyse von approximativen Algorithmen für verschiedene Probleme der kombinatorischen Optimierung vorgestellt. Weiter werden Grundlagen der Komplexitätstheorie vermittelt, um auch theoretisch fundierte Grenzen der algorithmischen Möglichkeiten aufzuzeigen.

Lernziele:

In diesem Modul werden die Studierenden mit neuen aktuellen Techniken des Entwurfes und der Analyse von approximativen Algorithmen und der Gewinnung von Inapproximierbarkeitsergebnissen vertraut gemacht. Die Studierenden erwerben die Fähigkeit, die vorgestellten Techniken systematisch auf viele klassische Probleme der kombinatorischen Optimierung anzuwenden.

Lehrinhalte:

Ausgewählte Themen aus dem Bereich der approximativen Algorithmen; insbesondere werden auch neuere Arbeiten aus der aktuellen Forschung hier vorgestellt.

Weitere Voraussetzungen:

Besuch der Vorlesung Einführung in die Algorithmik, Mathematik A und B oder äquivalente Vorlesungen.

Prüfungsleistung:

Prüfungsvorleistung ist die erfolgreiche Bearbeitung der Hausaufgaben (Übungsaufgaben). Die Übungsaufgaben gelten als bestanden, wenn

• der Student sich im Rahmen der Übung durch Vorrechnen aktiv beteiligt
• mindestens 40% der Punkte in den Übungsaufgaben (als Summe über alle Serien) erreicht werden
• Je Aufgabe reicht das Durchrechnen des richtigen Ansatzes (auch mit kleineren Fehlern) für volle Punktzahl (2 Punkte), sinnvolles Bearbeiten (richtiger Ansatz) reicht für die halbe Punktzahl (1 Punkt)
• jede Serie "sinnvoll bearbeitet" wird, wofür es insbesondere ausreicht, mindestens einen Punkt zu erhalten

Als Prüfungsleistung werden den Studierenden individuelle Forschungsaufgaben gestellt, welche die Studierenden bearbeiten müssen. Die Bewertung der Forschungsaufgabe ergibt sich aus 2 Teilen:

• Schriftliche Ausarbeitung (ca 8-15 Seiten) eines Forschungsergebnisses, z.B. Verbesserung eines Algorithmus bezüglich Laufzeit oder Approximationsgüte. Statt eines Forschungsergebnisses kann auch eine neue algorithmische Idee implementiert werden und eine Ausarbeitung dazu erstellt werden.
• Vortrag über Forschungsergebnis (bzw Vortrag über neue algorithmische Idee und Implementierung), Dauer ca. 30 min

Beide Teile der Bearbeitung der Forschungsaufgabe sind zu bestehen, damit diese als "erfolgreich bearbeitet" gilt. Bewertet werden die Übungsaufgaben und die Forschungsaufgabe je zu 50%. Die Note der Forschungsaufgabe wird, wenn sie besser als die Note zu den Übungsaufgaben ist, als Gesamtnote genommen.

Voraussetzung für das Bestehen des Moduls sind:

• Erfolgreiche Bearbeitung der Übungsaufgaben, d.h. es werden mindestens 40% der Gesamtpunktzahl erreicht. Die Note dieses Teils ergibt sich aus den erreichten Punkten im Verhältnis zu 80% der Gesamtpunktzahl.
• Aktive Mitarbeit in der Übung als Prüfungsvorleistung; "Aktive Mitarbeit" bezieht sich hierbei auf das Vorstellen der Hausaufgaben, was sich gleichmäßig auf alle Studenten verteilen soll.
• Erfolgreiches Bearbeiten der Forschungsaufgabe

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• Teofilo F. Gonzalez: Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall, 2007, ISBN-10: 1584885505.
• Dorit Hochbaum: Approximation Algorithms for NP-Hard Problems, 1996, ISBN-10: 0534949681.
• Juraj Hromkovic: Algorithmics for Hard Problems, Springer 2001, ISBN 3-540-44134-4.
• Klaus Jansen und Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, April 2008, ISBN 978-3-11-020316-5.
• Vijay Vazirani: Approximation Algorithms, Springer, 2001, ISBN 3-540-65367-8.
• Rolf Wanka: Approximationsalgorithmen: Eine Einführung, Vieweg und Teubner, 2006, ISBN 978-3-519-00444-8.
• David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011, ISBN 978-0-521-19527-0.

Verweise:

Kommentar: