Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-52-17-M-7

Approximation Algorithms (M, 9.0 LP)

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
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Module Manager
Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT)
Lecturers
Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT)
Ruzika, Stefan, Prof. Dr. (PROF | DEPT: MAT)
Area of study [MAT-OPT] Optimisation
Reference course of study [MAT-88.105-SG] M.Sc. Mathematics
Livecycle-State [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")

Evaluation of grades

The grade of the module examination is also the module grade.


Contents

From [MAT-52-17-K-7] Approximation Algorithms:
  • 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

From [MAT-52-17-K-7] Approximation Algorithms:
  • D. P. Williamson and D. P. Shmoys: The Design of Approximation Algorithms,
  • V. V. Vazirani: Approximation Algorithms.

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.)