TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Approximation Algorithms

Semester Sommersemester 2015 [ Andere Semester: Sommer 17 · Sommer 12 · Sommer 09 ]
Modulnr. INF-ALG-14
Veranst.Nr. INF-ALG-015 , INF-ALG-016
Studieng. Master Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR Gruppe(n) ALG (Prof. Fekete)
Art Vorlesung/Übung
Dozent
Photo Prof. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistent
Photo Dr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
alvarez[[at]]ibr.cs.tu-bs.de
LP 5
SWS 2+1+1
Ort & Zeit

Lecture: Tuesday, 15:00 - 16:30 Room PK 4.4
Exercises: Thursday, 09:45 - 11:15, Room PK 4.4, start: TBA.
Small Tutorial: TBA.

Beginn

Vorlesung: 21.04.2015, Grosse Uebung: TBA, Kleine Uebung: TBA

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

    • Schedule of all lectures, tutorials etc.: [PDF] [28.04.15]

    Homework Sets

    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 will be a mailing list. We will distribute the homework sets and other announcements via this list, so, please subscribe!
  • Videos


    aktualisiert am 29.06.2015, 16:01 von Prof. Dr. Sándor P. Fekete
    printemailtop