Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Team
  - Advent(2)
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
- Forschungsverbünde
  - IST.hub

Approximation Algorithms

Semester	Sommersemester 2012 Sommersemester 2023 Sommersemester 2021 Wintersemester 2019/2020 Sommersemester 2017 Sommersemester 2015 Sommersemester 2009
Modulnummer	INF-ALG-14
Veranstaltungsnummer	INF-ALG-015 , INF-ALG-016
Studiengänge	Informatik Master, Informations-Systemtechnik Master, Wirtschaftsinformatik Master
IBR Gruppe	ALG (Prof. Fekete)
Art	Vorlesung & Übung
Dozent	Prof. Dr. Sándor P. Fekete Abteilungsleiter s.fekete[[at]]tu-bs.de +49 531 3913111 Raum 335
Assistent	Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin
LP	5
SWS	2+1+1
Ort & Zeit	Lecture: Tuesday, 15:00 - 16:30 Room IZ161 Exercises: Thursday, 15:00 - 16:30, Room IZ161, start: TBA. Small Tutorial: Wednesday, 16:45 - 18:15, Room IZ161.
Beginn	Vorlesung: 17.04.2012, Grosse Uebung: 26.04.2012, Kleine Uebung: 02.05.2012
Voraussetzungen
Scheinerwerb	(Homework assignments during the semester, and)* an oral exam at the end. (*=Studienleistung)
Inhalt	Many interesting and natural algorithmic problems (e.g., the Traveling Salesman Problem) are NP-complete - hence, we cannot expect to find a "perfect" algorithm that (i) always and (ii) fast finds (iii) an optimal solution. However, hard problems still need to be solved! In this class we consider algorithms that do not necessarily find an optimal solution, but that (i) always and (ii) fast find a (iii) provably good solution. Prerequisites are knowledge of algorithms and data structures, basic graph problems and graph algorithms (e.g., as provided in the lecture "Netzwerkalgorithmen"); basic knowledge from theoretic computer science (NP-completeness) are helpful, but will definitely be supplemented. Among the topics of this class are: (1) A basic introduction to NP-completeness and approximation (2) Approximation for vertex and set cover (3) Packing problems (4) Tour problems and variations (5) Current research problems In the context of various problems, a wide spectrum of techniques and concepts will be provided.
Announcements and Dates General Information Two lectures will take place in the tutorial slot: lecture from June 12, on June 14; and lecture from June 19 on June 25. Schedule of all lectures, tutorials etc.: [PDF] [12.04.12] Homework Sets homework set 0: [PDF] homework set 1: [PDF] homework set 2: [PDF] homework set 3: [PDF] homework set 4: [PDF] homework set 5: [PDF] Literature: Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001. Approximation Algorithms for NP-hard problems edited by Dorit S. Hochbaum, more info. mailing list There is a mailing list. We will distribute the homework sets and other announcements via this list, so, please subscribe! In case of technical difficulties pleas send an email to Christiane. material for the class material for the class (videos)