# 186.102 Approximation Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});});

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

## Properties

• 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

ECTS-Breakdown:

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

DayTimeDateLocationDescription
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

## Literature

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

German