max planck institut
informatik
informatik
| Lecture time: | Fridays 10-12 |
|---|---|
| Lecture room: | E1.4 Room 0.24 |
| Lecturer: | Matthias Mnich |
| Tutorial time: | Thursdays 2-4pm |
| Tutorial room: | Building E1 7, Room 3.23 (except May 10: Building E1 4, Rotunde 2nd floor) |
| Tutor: | Megha Khosla |
| Audience: | The course counts as computer science lecture (2 SWS, 6 CP). The lecture will be given in English. |
| Information: | The first lecture will take place on Friday, April 20th. |
| Exercises: | We will hand out exercises every week. For admission for the final exam, you have to (1) achieve at least 40% of the possible points and (2) present a solution at least twice in a tutorial. The points in the exercises do NOT count towards the final grade of the exam. |
| Final Exam Date: | 27 July 2012, 12pm - 2pm, Room 0.24 in Building E1 4. |
| Re-Exam Date: | to be determined |
| Reference books: | Most of the course material is covered in
Fedor Fomin and Dieter Kratsch: Exact Exponential Algorithms |
Many fundamental problems in theoretical computer science have been classified as "intractable", meaning that no "efficient" algorithm to solve them is known or likely to exist. As this is no excuse for not solving these problems, algorithms have been designed that produce solutions of different qualities, compared to an optimal solution. Popular kinds of algorithms for intractable problems are heuristics, that aim for good-quality solutions for instances occurring in practice but for which no such quality can be guaranteed, and approximation algorithms, that produce solutions for which the ratio between the quality of a produced solution and an optimal solution can be bounded, for all possible instances. Both kinds of algorithms are efficient, that is, the time required by them to produce a solution is bounded by a polynomial in the size of the input instance. Another kind of algorithms for intractable problems is the topic of this course: exponential-time algorithms, that always return an optimal solution for any instance. Our objective is to design exponential-time algorithms running in time that is "moderate" for instances of relatively small size. That means, their time requirement is provably (and desirably significantly) less than that of exhaustively searching through all feasible solutions for an optimal one. With this course we aim to give an introduction into this very active area of research.