186.102 Approximation Algorithms
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2018W, VU, 2.0h, 3.0EC, to be held in blocked form


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Aim of course

- Understanding the basic terms of exact and approximative solutions
- Being able to analyze approximation ratios
- Knowing classical approximability results for discrete optimization problems
- Being able to understand published articles in the area of approximation algorithms 

Subject of course

- Measure of quality for approximation algorithms
- Basic schemes of heuristics and methods to determine the approximation ratio
- Heuristics and their analysis for Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover and Set Cover Probleme

Additional information


21h   lecture time
20h   preparation of homework assignments
  6h   presentation of homework assignments
25h   preparation for final exam
  3h   final exam
75h   total 



Course dates

Thu15:00 - 18:0018.10.2018Seminarraum FAV 05 (Seminarraum 186) Approximation Algorithms
Fri15:00 - 18:0019.10.2018Seminarraum FAV 05 (Seminarraum 186) Approximation algorithms
Wed15:00 - 17:0031.10.2018 Seminar Room 183/2Approximation Algorithms
Thu15:00 - 18:0008.11.2018Seminarraum FAV 05 (Seminarraum 186) Approximation Algorithms
Thu14:30 - 17:0015.11.2018Seminarraum FAV 05 (Seminarraum 186) Apprximation Algorithms
Thu16:00 - 19:0022.11.2018Seminarraum FAV 01 A (Seminarraum 183/2) Approximation Algorithms
Fri15:00 - 18:0023.11.2018Seminarraum FAV 05 (Seminarraum 186) Approximation Algorithms
Mon15:00 - 17:0026.11.2018 Seminarraum 183/2Approximation Algorithms
Mon15:00 - 17:0003.12.2018 Seminarraum 183/2Approximation Algorithms
Mon15:00 - 17:0010.12.2018Seminarraum FAV 01 A (Seminarraum 183/2) Approximationsalgorithmen
Mon15:00 - 17:0017.12.2018Seminarraum FAV 01 A (Seminarraum 183/2) Written Exam
Course is held blocked

Examination modalities

- Three exercise sheets
- active participation
- oral exam (approx. 20 Min.) after completion of the course.

Course registration

Begin End Deregistration end
01.10.2018 00:00 16.10.2018 23:59



K.  Jansen, M.  Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.

R. Wanka, Approximationsalgorithmen: Eine Einführung, Teubner, 2006.

D.S. Hochbaum,  Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997.

V.V. Vazirani,  Approximation Algorithms,  Springer, 2001.

G. Ausiello et al., Complexity & Approximation, Springer, 1999.

Previous knowledge

knowledge of basic algorithms and data structures, basic proof techniques

Accompanying courses