# 186.102 Approximation Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",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_22",{id:"j_id_22",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2021W 2019W 2018W 2018S 2017S 2016S 2015S 2014S 2013S 2012S 2011S 2010S 2009S 2008S 2007S 2006S 2005S 2004S 2002W

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

## Properties

• 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

Immanent

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
Fri15:00 - 18:0008.10.2021Seminarraum FAV 05 (Seminarraum 186) Lecture
15:00 - 18:0014.10.2021 - 15.10.2021Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu15:00 - 18:0021.10.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fri15:00 - 18:0005.11.2021Seminarraum FAV 05 (Seminarraum 186) Lecture
15:00 - 18:0018.11.2021 - 19.11.2021Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri13:00 - 16:0026.11.2021Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fri15:00 - 18:0003.12.2021Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri15:00 - 18:0014.01.2022Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Approximation Algorithms - Single appointments
DayDateTimeLocationDescription
Fri08.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu14.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri15.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu21.10.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fri05.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu18.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri19.11.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri26.11.202113:00 - 16:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Fri03.12.202115:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Fri14.01.202215:00 - 18:00Seminarraum FAV 05 (Seminarraum 186) Vorlesung
Course is held blocked

## 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
27.09.2021 00:00 05.10.2021 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