Technische Universität Ilmenau

Approximation Algorithms - Interactive curriculae of TU Ilmenau

The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the course catalogue.

Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.

module properties Approximation Algorithms in degree program Master Informatik 2013
ATTENTION: not offered anymore
module number200077
examination number2200731
departmentDepartment of Computer Science and Automation
ID of group 2242 (Algorithms)
module leaderProf. Dr. Martin Dietzfelbinger
term winter and summer term
languageDeutsch
credit points5
on-campus program (h)67
self-study (h)83
obligationelective module
examoral examination performance, 30 minutes
details of the certificate
link to Moodle course
teacherDietzfelbinger
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.

Sozialkompetenz: Selbst in der Vorlesung ist Interaktion stets möglich, dazu sind die Studierenden befähigt. Die Studierenden haben die Erfahrung gemacht, dass Fragen unmittelbar geklärt werden, dass Diskussionen auf Augenhöhe stattfinden und Beiträge wertschätzend aufgenommen werden. In der Übung konnten sich die Studierenden in Präsentationen üben. Sie haben wertvolle Erfahrung in der Rolle des Präsentierenden. 


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 and technical requirements for education and examination in case of online participation

 zum Moodle-Kurs

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