Berechenbarkeit, Komplexität und Approximation
Teacher:
Prof. Dr. Petra Berenbrink
Content:
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.
First section is about the concept of NP-Completenes. The second covers the combinatorial algorithms for several well-known Problems using a wide variety of algorithm design techniques.
Preliminaries:
Students should be familiar with basic concepts and methods relevant to the areas of computer science. They need to be cable of understanding the mathematical proofs.
Procedure:
The class will be held as a reading class.
-
Every Wednesday we will send our pointers to the reading material and a problem sheet (first time April 22).
-
One week later (during the time slot of the class) we will meet online and discuss the reading material handed out the week before. We will go through the material together and we will answer questions. Note: we assume that every student used the week to have a close look at the class material!
On April 22 we will meet online for the first time and the teacher will explain the class concept to all of you.
-
The exercise classes will be held online. There is one problem sheet per week. It consists of four questions, two of them have to be handed in. Solutions will be corrected and students will have to solve half of the questions in total. Students will have to present at least two question in the exercise classes. The exercise classes start in the second week of the term.
Please send an e-mail to the tutor a couple of days before the exercise class if you would like to present your solution. The tutor will schedule the student presentations in a fair way and let you know beforehand. This enables students to prepare themselves for the presentation.
-
On 4 days per week you will have the opportunity to ask questions via on-line meetings with a tutor. These question hours are scheduled together for BKA and FGI 1. Please state to the tutor which class you are taking. Details will be available later.
The communication takes place through Bigbluebotton and Zoom. You can find the application in the link section. Please let us know if you have any problems with these arrangements so that we can find another solution.
Litrature:
There are several principal books.
- Sipser, Introduction to the Theory of Computation ( 3th edition)
- Vazirani, Vijay V., Approximation Algorithms. (2010) Springer
- Cormen et al, Introduction to Algorithms (3th edition)
Assignments:
Here you can find the problem sheets.
Links:
Qualification:
To pass the exercise class you will have to present 2 solutions in the exercise classes and you need 50% on the problem sheets. At this moment we assume that there will be a final at the end of this class.