# 186.102 Approximation Algorithms CanceledThis 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"});}); 2023W 2022W 2021W 2019W 2018W 2018S 2017S 2016S 2015S 2014S 2013S 2012S 2011S 2010S 2009S 2008S 2007S 2006S 2005S 2004S 2002W

2022W, 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

---

## 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

## Curricula

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

## 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