Dozent: Dr. Anusch Taraz
Termine
Beginn und Themenvergabe: 08.05.2002| PS | Mittwoch | 16:00 - 18:00 | (DOR 24, 311) |
|---|
Zuordnung
- Grundstudium, Proseminar
Voraussetzungen
- Empfohlen: Theoretische Informatik 2
Inhalte und Lernziele
Das Traveling Salesman Problem befasst sich damit, eine möglichst kurze Route durch gegebene Orte zu finden, und ist eines der Urprobleme der kombinatorischen Optimierung. Wir untersuchen exakte, approximative und randomisierte Lösungsverfahren.
Themen
- Einführung: Geschichte, Motivation, Modelle
- Exakte Algorithmen
- Komplexität
- Nearest Neighbour und Minimum spanning tree Heuristik
- Christofides Approximation
- Approximationsschemata
- Probabilistische Analyse
- Berühmte Spezialfälle
Empfohlene Literatur
- , The Traveling Salesman Problem, Wiley, 1985
