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.

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

Additional information

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 


Lecturers

Institute

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

Curricula

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

Accompanying courses

Language

German