Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Course MAT-52-17-K-7

Approximation Algorithms (4V+2U, 9.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 9.0 CP 186 h
4 V Lecture 56 h
2 U Exercise class (in small groups) 28 h
(4V+2U) 9.0 CP 84 h 186 h

Basedata

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Lecturers
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

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

Literature

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

Materials

Further literature will be announced in the lecture; Exercise material is provided.

Registration

Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de)

References to Course [MAT-52-17-K-7]

Module Name Context
[MAT-52-17-M-7] Approximation Algorithms P: Obligatory 4V+2U, 9.0 LP