Termine
| PS |
Freitag |
11:00 - 13:00 |
(RUD 25, 4.101) |
Achtung! Die Themenvergabe ist am Donnerstag 17. April 2003, 15-17 Uhr, RUD 25, 1.011.
Zuordnung
Voraussetzungen
- Empfohlen: Theoretische Informatik 2
Inhalte und Lernziele
Approximationsalgorithmen sind ein guter Kompromiss, wenn man ein
Optimierungsproblem lösen soll, das NP-schwer ist. Sie lösen das
Optimierungsproblem nicht exakt, sondern liefern eine Lösung, deren Wert
vom Optimum höchstens um einen bestimmten Faktor abweicht. Wir
beschäftigen uns in diesem Proseminar mit Beispielen von
Approximationsalgorithmen für kombinatorische Optimierungsprobleme.
Vortragsthemen
| Datum | Thema |
|---|
| 17.04. | Einführung |
|---|
| 02.05. | Set Cover |
|---|
| 09.05. | Matchings |
|---|
| 16.05. | TSP mit Dreiecksungleichung |
|---|
| 23.05. | Shortest Superstring |
|---|
| 30.05. | Das k-Zentrumsproblem |
|---|
| 06.06. | Scheduling |
|---|
| 13.06. | Scheduling mit Freigabezeiten |
|---|
| 20.06. | Minimum degree spanning trees |
|---|
| 27.06. | Steinerbäume (Minimum spanning tree Heuristik) |
|---|
| 04.07. | Steinerbäume (Berman,Ramaiyer) |
|---|
| 11.07. | MaxSAT/MaxCut mit bedingten Erwartungen |
|---|
Empfohlene Literatur
-
D. Hochbaum (ed.),
Approximation Algorithms for NP-hard Problems,
PWS Publishing, 1995.
-
V.V.Vazirani,
Approximation Algorithms,
Springer, 2001.
English