Approximations- und Onlinealgorithmen
| Content: |
| Verschiedene wichtige und in der Praxis häufig auftretende Optimierungsprobleme lassen sich nicht in Polynomialzeit lösen (bei P ungleich NP), eine exakte Lösung erfordert somit sehr großen Zeitaufwand. Daher versucht man häufig Näherungslösungen zu erzielen, die man effizient, d.h. in Polynomialzeit, finden kann. Von Interesse ist dann natürlich, welche Qualität der erhaltenen Lösung man garantieren kann. Vorgestellt und analysiert werden algorithmische Approximationsverfahren für verschiedene typische Probleme, an denen man gut geeignete Lösungstechniken erlernen kann. Auch wird die Online-Situation betrachtet, wenn die Eingabe nur sukzessive bekannt wird. Ein typisches Problem ist hierbei etwa das Bahncard-Problem (oder das American Airlines-Problem), wobei der Kauf einer Bahncard die Kosten von Fahrkarten für eine bestimmte Zeit um 25% bzw. 50% reduziert. Die in der Vorlesung vorgestellten Techniken werden in den zugehörigen Übungen angewandt und vertieft. |
| Literature: |
|
| Participants: |
| IF7, AIF7, MA; Interessierte Studierende der Informatik und Angewandten Informatik im Hauptstudium und ggf. Studierende verwandter Fachrichtungen. |
| Exam: |
| oral examination |
| Exercises: |
