TU BRAUNSCHWEIG
| Carl Friedrich Gauß Faculty | Department of Computer Science
Informatikzentrum

Approximation Algorithms

SemesterWinter 2019/2020 [ Other terms: · Sommer 17 · Sommer 15 · Sommer 12 · Sommer 09 ]
Module #INF-ALG-14
Event # INF-ALG-015 , INF-ALG-016
ProgrammesMaster Wirtschaftsinformatik, Master Informations-Systemtechnik, Master Informatik
IBR Group(s)ALG (Prof. Fekete)
TypeVorlesung/Übung
Lecturer
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistants
PhotoPhillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Room 318
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 315
Hiwi
Anonymous PhotoVictoria Sack
Studentische Hilfskraft
sack[[at]]ibr.cs.tu-bs.de
Credits5
Hours2+1+1
Time & Place

Lecture: Tuesdays, 15:00-16:30, SN 19.2
Tutorial and Homework Discussion: Wednesday, 11:30-13:00, SN 19.4

Start

Lecture: October, 29th, Exercises: TBA, small Tutorial: TBA

Prerequisites

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.

Certificates (Homework assignments during the semester, and)* an oral exam at the end. (*=Studienleistung)
Content

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.

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.

General Information

  • We do only use this website and the below mentioned mailinglist to distribute informations. No studip etc.
  • If there are any questions, do not hesitate to write a mail.

Homework Sets

There will be biweekly mandatory homework. Please check the material area.

Literature:

The first part of the lecture will be on basic results for which the following books can be useful
  • Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001.
  • Approximation Algorithms for NP-hard problems edited by Dorit S. Hochbaum, more info.
  • The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, published by Cambridge University Press. more info
The second part of the lecture will be on recent results for which the corresponding papers will be announced in due time.

Mailing List

There will be a mailing list. We will distribute the homework sets and other announcements via this list, so, please subscribe!

You may also want to check out the alg-studs mailing list which is similiar to cs-studs but for algorithmic students.


last changed 2019-10-15, 11:32 by Dominik Krupke
printemailtop