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

Approximation Algorithms

Semester
ModulnummerINF-ALG-27
Veranstaltungsnummer INF-ALG-015 , INF-ALG-016
StudiengängeMaster Wirtschaftsinformatik, Master Informatik, Master Informations-Systemtechnik
IBR GruppeALG (Prof. Fekete)
ArtVorlesung/Übung
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter

+49 531 3913111
Raum 335
Assistenten
PhotoDr. Phillip Keldenich
Wissenschaftlicher Mitarbeiter

+49 531 3913112
Raum 318
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter

+49 531 3913116
Raum 332
LP5
SWS2+1+1
Ort & Zeit

Lecture: Online, Tuesday 3 PM - 4:30 PM.
Tutorial and Homework Discussion: Online, Wednesday, 11:30 AM - 1 PM.

Beginn

First lecture: Tuesday, 20.4.2021, 3 PM.

Voraussetzungen

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 theoretical computer science (NP-completeness) are helpful, but will definitely be supplemented.

Scheinerwerb Homework assignments throughout the semester (Studienleistung) and an oral exam (probably online) at the end of the semester (Prüfungsleistung).
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.

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 only use this website and the mailinglist mentioned below to distribute informations; the information on other sites such as StudIP etc. may be missing or outdated.
  • If there are any questions, do not hesitate to write a mail.

Video recordings

For the first lectures, we will make use of video recordings of the previous version of this course. Please do not hesitate to contact us if there are any problems with the videos. If you do encounter a problem while playing the recordings in your browser, consider downloading the video and playing it in a regular video player.

Homework Sets

The homework assignment sheets can be found below.

Literature

The first part of the lecture will be on classic results for which the following books can be useful.

  • Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001 [PDF].
  • 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 (online). 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 similar to cs-studs but for algorithmic students.


aktualisiert am 06.05.2021, 18:53 von Dr. Phillip Keldenich
printemailtop