Termine
Beginn:
19.04.2002
| SE |
Freitag |
09:00 - 11:00 |
(RUD 25, 3.101) |
Zuordnung
Voraussetzungen
Inhalte und Lernziele
Für eine Reihe von diskreten Optimierungsproblemen sind keine exakten
Algorithmen akzeptabler Komplexität bekannt. Daher sollen in diesem
Seminar Algorithmen zur Bestimmung von Näherungslösungen solcher
Probleme diskutiert werden. Den Schwerpunkt werden dabei
nicht-kombinatorische, also zum Beispiel auf linearen Programmen
basierende, zum Teil randomisierte Techniken bilden.
Vortragsthemen
Bisher sind zu folgenden Themen Vorträge beabsichtigt:
| 19.04. |
|
Einführung |
| 3.05. |
Rodrigo Witzel |
Kombinatorische Algorithmen: Steinerbaum und TSP |
| 17.05. |
Mia Viktoria Meyer |
LP-Dualität |
| 24.05. |
|
Die Ellipsoid-Methode |
| 31.05. |
Christian Düster |
Kombinatorische Optimierung durch Lineares Programmieren |
|
|
Semidefinite Programmierung (SDP) |
|
|
Anwendungen von SDP auf Graphenprobleme |
|
|
Nichtapproximierbarkeit |
Empfohlene Literatur
-
V. Vazirani,
Approximation Algorithms,
Springer 2001.
-
V. Chvátal,
Linear Programming,
Freeman 1983.
-
R. Motwani, P. Raghavan,
Randomized Algorithms,
Cambridge 1995.
-
M. Grötschel, L. Lovasz, A.Schrijver,
Geometric Algorithms and Combinatorial Optimization,
Springer 1988.
-
A. Schrijver,
Theory of Linear and Integer Programming,
Wiley 1986.
-
Th. Emden-Weinert et al.,
Einführung in Graphen und Algorithmen.
