## Module Handbook

• Dynamischer Default-Fachbereich geändert auf MAT

# Module MAT-52-17-M-7

## Module Identification

Module Number Module Name CP (Effort)
MAT-52-17-M-7 Approximation Algorithms 9.0 CP (270 h)

## Basedata

CP, Effort 9.0 CP = 270 h 1 Sem. irreg. [7] Master (Advanced) [EN] English Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Ruzika, Stefan, Prof. Dr. (PROF | DEPT: MAT) [MAT-OPT] Optimisation [MAT-88.105-SG] M.Sc. Mathematics [NORM] Active

## Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U MAT-52-17-K-7
Approximation Algorithms
P 84 h 186 h - - PL1 9.0 irreg.
• About [MAT-52-17-K-7]: Title: "Approximation Algorithms"; Presence-Time: 84 h; Self-Study: 186 h

## Examination achievement PL1

• Form of examination: oral examination (20-30 Min.)
• Examination Frequency: irregular (by arrangement)
• Examination number: 86145 ("Approximation Algorithms")

## Contents

• basics of approximation algorithms and approximation schemes (PTAS, FPTAS),
• Greedy algorithms and local search,
• approximate dynamic programming,
• deterministic and randomized rounding,
• primal-dual method,
• proof techniques for lower bounds on achievable approximation quality (GAP preserving reductions).

## Competencies / intended learning achievements

Upon successful completion of this module, the students have mastered various techniques for designing approximation algorithms for optimization problems. They are able to analyze these algorithms and to apply them to specific problems. They know and understand techniques to prove lower limits to the achievable approximation quality and they are able to critically assess the possibilities and limitations of the use of the algorithms. They understand the proofs presented in the lecture and are able to comprehend and explain them. In particular, they are able to outline the conditions and assumptions that are necessary for the validity of the statements. Moreover, they have learnt how to apply these techniques to new problems, analyze them and develop solution strategies independently or by team work. They have studied various techniques for limiting the target function values of solutions (optimal and approximate) and are able to transfer these to new problems.

By completing the given exercises, the students have developed a skilled, precise and independent handling of the terms, propositions and techniques taught in the lecture.

## Literature

• D. P. Williamson and D. P. Shmoys: The Design of Approximation Algorithms,
• V. V. Vazirani: Approximation Algorithms.

None

## References to Module / Module Number [MAT-52-17-M-7]

Module-Pool Name
[MAT-52-MPOOL-7] Specialisation Mathematical Optimisation (M.Sc.)
[MAT-AM-MPOOL-7] Applied Mathematics (Advanced Modules M.Sc.)