Technische Universität Ilmenau

Approximation Algorithms - Modultafeln of TU Ilmenau

The Modultafeln have a pure informational character. The legally binding information can be found in the corresponding Studienplan and Modulhandbuch, which are served on the pages of the course offers. Please also pay attention to this legal advice (german only). Information on place and time of the actual lectures is served in the Vorlesungsverzeichnis.

subject properties Approximation Algorithms in major Master Informatik 2009
subject number230
examination number2200078
departmentDepartment of Computer Science and Automation
ID of group 2242 (Group for Complexity Theory and Efficient Algorithms)
subject leaderProf. Dr. Martin Dietzfelbinger
term ganzjährig
languageDeutsch
credit points4
on-campus program (h)34
self-study (h)86
Obligationobligatory elective
examoral examination performance, 30 minutes
details of the certificate

Findet statt im: SS 2014, WS 2015/2016

Signup details for alternative examinations
maximum number of participants
previous knowledge and experience

Berechenbarkeit und Komplexitätstheorie, Effiziente Algorithmen

learning outcome

Fachkompetenz: Die Studierenden kennen die grundlegenden Konzepte des Bereichs der Approximationsalgorithmen, insbesondere die Definition von Optimierungsaufgaben und die Qualitätsstufen von Approximationsalgorithmen (absolute, relative Approximationsgüte, [voll] polynomielle Approximationsschemata, inputabhängige Approximation). Sie kennen die Wirkungsweise der relevanten Entwurfsprinzipien. Sie kennen die relevanten Analysetechniken. Die Studierenden kennen die zentralen Beispielprobleme, für die Approximationsalgorithmen entwickelt wurden, ihre Performanzparameter und die Analysemethode.

Methodenkompetenz: Die Studierenden können die Entwurfsprinzipien auf verwandte Problemstellungen anwenden. Sie können Algorithmen und Probleme in die relevanten Klassen APX, PTAS, FPTAS usw. einsortieren. Sie können die zentralen Algorithmen beschreiben und die Analyse durchführen.

content

Grundbegriffe. Einführende Beispiele. Greedy Set Cover. Absolute Approximation: Färbung von planaren Graphen, Kantenfärbungen. Relative Approximation. Greedy-Verfahren und ihre Analyse.  MAX-SAT, Metrisches TSP. Asymptotische relative Approximation. Inputabhängige Approximation: Graphfärbungen. Polynomielle Approximationsschemata: Rucksackproblem. Asymptotisches Approximationsschema: Binpacking. Weitere Techniken: Lineare Programmierung und Randomisiertes Runden am Beispiel von MAX-SAT. Derandomisierung. Semidefinite Programmierung am Beispiel von Max-Cut. Approximate Counting und die Monte-Carlo-Methode.

media of instruction

Folien, Tafel, Übungsblätter

literature / references

* R. Wanka, Approximationsalgorithmen, Teubner 2006 

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

 * G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation, Springer-Verlag 1999

* D. P. Williamson, D. P. Shmoys, The Design of Approximation Algorithms, Cambridge University Press 2011

* D.-Z. Du, K.-I Ko, X. Hu, Design and Analysis of Approximation Algorithms, Springer 2012.

evaluation of teaching

Pflichtevaluation:

Freiwillige Evaluation:

WS 2009/10 (Übung)

Hospitation: