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.

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

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

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