- 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).
Approximation Algorithms (M, 9.0 LP)
|Module Number||Module Name||CP (Effort)|
|MAT-52-17-M-7||Approximation Algorithms||9.0 CP (270 h)|
|CP, Effort||9.0 CP = 270 h|
|Position of the semester||1 Sem. irreg.|
|Level|| Master (Advanced)|
|Area of study||[MAT-OPT] Optimisation|
|Reference course of study||[MAT-88.105-SG] M.Sc. Mathematics|
|Type/SWS||Course Number||Title||Choice in |
|SL||SL is |
required for exa.
|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.
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.
- D. P. Williamson and D. P. Shmoys: The Design of Approximation Algorithms,
- V. V. Vazirani: Approximation Algorithms.
Requirements for attendance of the module (informal)
- [MAT-10-1-M-2] Fundamentals of Mathematics (M, 28.0 LP)
- [MAT-14-13-M-3] Linear and Network Programming (M, 9.0 LP)
- [MAT-50-11-M-4] Integer Programming: Polyhedral Theory and Algorithms (M, 9.0 LP)