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

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


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

Learning outcomes

After successful completion of the course, students are able to...

- explain the difference between exact and approximative solutions
- analyze the approximation ratios of algorithms
- reproduce classical approximability results for discrete optimization problems
- 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

Teaching methods

Discussion of examples, solving exercises and presenting results in the lecture

Mode of examination


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 




Examination modalities

After a successful completion of the course, students are able to understand the complexity respectively the approximability status of discrete optimization problems. Moreover, they have the theoretical basics for doing a worst-case analysis for a given approximation algorithm.

Course registration

Begin End Deregistration end
03.10.2022 00:00 11.10.2022 23:59


Study CodeObligationSemesterPrecon.Info
066 645 Data Science Not specified
066 646 Computational Science and Engineering Not specified
066 931 Logic and Computation Mandatory elective
066 932 Visual Computing Mandatory elective
066 937 Software Engineering & Internet Computing Mandatory elective


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