Lectures Held on a Regular Basis

Please click here to find the lectures that are held on a regular basis. This information can be used to create a study plan. However, this information is tentative, i.e. always check the lectures of the current and next semester to keep the study plan up to date.

Lectures of the Current Semester

Module details on 'Approximation Algorithms - Approximation Algorithms'

CategoryTheoretical Foundations
LecturerProf. Dr. Fekete, Sándor (Braunschweig)
Module Exam ID1070
Weekly Composition2L+1E
Required Hours of Work (presence / self-study)125 (42 / 83)
SemesterSummer (biyearly)
Teaching MethodsBlackboard lecture/video-taped
Module DescriptionMany 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.
Module OutcomesOn completion of this module, the student knows the necessity and the eligibility of distributed algorithms. He/she is proficient in the most important techniques for approximation algorithm analytics and design. In addition, students will be able to analyze current state-of-the-art literature, evaluate the finer points, and apply principles and methods in a variety of scenarios.
Recommended LiteratureVazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, 2001. Approximation Algorithms for NP-hard problems edited by Dorit S. Hochbaum, PWS Publishing, 1997
PrerequisitesBasic knowledge and experience with algorithms, as obtained in undergraduate classes on algorithms and data structures and discrete algorithms
ExamWritten or oral exam, graded (120min (if written), 25 min (if oral))

Available Course Modes

In the following document you can get an overview about the available course modes that are offered in the ITIS Master's program: Course Modes