Inhalt
Fortgeschrittene Themen des Algorithmenentwurfs mit wechselnden Schwerpunkten.
Thema des Seminars ist diesmal die Betrachtung von Algorithmen für "schwere Probleme". Wie wir ja aus der Komplexitätstheorie wissen, gibt es zahlreiche algorithmische Probleme die schwer für eine Komplexitätsklasse sind. Das heißt, dass ein effizienter Algorithmus für ein solches Problem effiziente Algorithmen für die gesamte Klasse liefern würde (z.B. NP-schwer, NP-hard) und daher sehr unwahrscheinlich ist. Sehr viele in der Praxis auftretende Probleme haben diese Eigenschaft, die aber dennoch gelöst werden müssen. Verschiedene Techniken wurden dafür entwickelt, die im Seminar betrachtet werden sollen:
-- Approximationsalgorithmen
-- exakte Algorithmen exponentieller Laufzeit im schlechtesten Fall, der aber selten auftritt
-- LP-Relaxierung, dh. Reduktion des Problems auf (ganzzahliges) lineares Programmieren
-- Metaheuristiken, (simulated annealing, genetische Algorithmen)
Zielgruppe
Master-Studierende der Informatik oder Mathematik
Required Background
Course "Höhere Algorithmik" or a comparable course.
Language
The seminar will be in English.
Requirements
The main requirement is a lecture of 70 minutes given by each participant.
A lengthy written seminar workout is not required, just 4 pages pdf summary sent to the instructor before the talk.
Literature
Books:
[CLR] Cormen, Leiserson, Rivest, Stein (2. Aufl.)
Introduction to Algorithms
[JM]
Jansen, Margraf
Approximative Algorithmen und Nichtapproximierbarkeit
[KT] Kleinberg, Tardos
Algorithm Design
[H] Hromkovic
Algorithms for Hard Problems
Design of Approximation Algorithms
Sowie Spezialliteratur aus Zeitschriften
Vortragsthemen
No meetings on April 26 and May 24 !
1. Meeting, May 3
Wenli Xu
approximation algorithms, simple examples, definitions
Approximationsalgorithmen
einfache Beispiele, Definitionen [JM] Kap. 1
2.
May 10
Myrthe Willemsen
Examples, Vertex Cover, Min-Job-Scheduling, Non-Approximability of TSP
Beispiele
Vertex Cover [CLR]
MIN-Job-Scheduling [JM] 6.1
Nichtapproximierbarkeit von TSP
3.
May 17
Viktor Skoblin
Approximation Algorithms for Delta-TSP
Approximationsalgorithmen für Delta-TSP [JM]6.2
4.
May 31
Helmut Alt
Simulated Annealing [KT] 12.1, 12.2
5.
June 7
Rui Zhao
FPTAs
AA. für Knapsack [CLR]
6.
June 14
Fatemeh Tavakkoli
BIN-Packing und Strip-Packing,
aus [JM] Kap. 7
7. June 21
Neda Rajabian
Linear Programming
Lineare Programmierung [CLR] 29.2
8. June 28
Helmut Alt
LP-Relaxation
weighted vertex cover
9. cancelled
Mouadh Khlifi
Exact Algorithms
Exakte Algorithmen
Einführung [FK] Kap.1
10. cancelled
Doruntina Murtezaj
Branching [FK] Kap.2
11. July 12
Mohannad Nouh
Random Walk und SAT [JM] Kap. 10.1 - 10.4.
12. July 19
Hongmiao Wu
FPT
[H] 3.3