64-074 Lecture Computability, Complexity and Approximation

Course offering details

Instructors: Prof. Dr. Petra Berenbrink

Event type: Lecture

Displayed in timetable as: BKA - VL

Hours per week: 3

Language of instruction: German

Min. | Max. participants: - | 240

Comments/contents:
Most natural optimization problems are NP-hard. Their exact solution is prohibitively time consuming, under NP ?= P. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. The lecture consists of two parts. We present an introduction to complexity theory with focus on NP-completeness and an introduction to combinatorial approximation algorithms.

 

Appointments
Date From To Room Instructors
1 Tue, 4. Apr. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
2 Tue, 11. Apr. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
3 Tue, 18. Apr. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
4 Tue, 25. Apr. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
5 Tue, 2. May 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
6 Tue, 9. May 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
7 Tue, 23. May 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
8 Tue, 30. May 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
9 Tue, 6. Jun. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
10 Tue, 13. Jun. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
11 Tue, 20. Jun. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
12 Tue, 27. Jun. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
13 Tue, 4. Jul. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
14 Tue, 11. Jul. 2023 16:15 18:45 Audimax 2 Prof. Dr. Petra Berenbrink
Exams in context of modules
Module (start semester)/ Course Exam Date Instructors Compulsory pass
Class session overview
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  •  
Instructors
Prof. Dr. Petra Berenbrink