LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hauptseminar WS 01/02
Die Welt der Handlungsreisenden: Algorithmen, Analysen und Anwendungen


Donnerstag, 14:15 bis 15:15 Uhr, S2229

[Zusammenfassung] [Themen und Literatur] [Hinweise]


Zusammenfassung

Ein Handlungsreisender möchte ausgehend von seiner Heimatstadt eine Serie von Städten bereisen. Er will die Städte in einer Reihenfolge besuchen, so dass die gesamte Reisestrecke möglichst klein wird. Er fragt sich also, was die beste Reihenfolge der Städte ist. Dieses Problem wird auch das Problem des Handlungsreisenden, oder kurz TSP (engl. Traveling Salesman Problem) genannt.

Das TSP ist eines der bekanntesten Probleme aus der kombinatorischen Optimierung und - auch wenn ganz einfach formuliert - ausgesprochen schwierig zu lösen. Da es zu den sogenannten NP-vollständigen Problemen gehört, wird es wohl auch keinen polynomiellen Algorithmus zum Auffinden einer Optimallösung geben. Trotzdem, TSP tritt häfig in verschiedenen Varianten in der Praxis auf, und es ist mittlerweile gelungen auch vergleichsweise größe Probleme optimal zu lösen. Wie dies gelingen kann, wollen wir in diesem Hauptseminar untersuchen.

Anhand des TSP werden dabei die wichtigsten algorithmischen Methoden der Kombinatorischen Optimierung vorgestellt. Wir analysieren verschiedene heuristische Verfahren und Approximationsalgorithmen, betrachten optimal lösbare Spezialfälle und beschreiben die Grundlagen fü Branch-and-Cut Verfahren. Ziel dieses Hauptseminars ist dabei, nicht nur ein einziges Problem zu lösen, sondern allgemeine Techniken zum Lösen von Optimierungsproblemen kennenzzulernen und zu vergleichen.

Neben der Algorithmenanalyse betrachten wir verschiedene Anwendungen, wie z.B. in der Fahrzeugeinsatzplanung oder der Bioinformatik und zeigen auch für diese verschiedenen Lösungsansätze auf.


Themen- und Literatur-Liste

Dem Seminar liegen folgende Bücher zugrunde:

Thema Titel Vortragende(r) Termin Betreuer
1 Einführung und Überblick über das TSP Problem Jabara Zakaria 25.10.01 Ulrich Rührmair
2 Heuristische Algorithmen für das TSP Daniel Wasserrab 08.11.01 Thomas Schickinger
3 Approximationsalgorithmen Bertold Meier 15.11.01 Thomas Bayer
4 Untere Schranken der Approximierbarkeit Nina Istavrinos 22.11.01 Martin Raab
5 Das Approximationsschema von Arora Andreas Weissel 29.11.01 Mark Scharbrodt
7 Schnittebenenverfahren für das TSP Problem Jiming Yin 13.12.01 Michal Mnuk
6 Probabilistische Analyse von Instanzen im Einheitswürfel Christian Osendorfer 20.12.01 Hanjo Täubig
8 Hamiltonkreise in Zufallsgraphen Markus Holm 10.01.02 Mark Scharbrodt


Hinweise zur Gestaltung der Vorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tips auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Tips zur Erstellung einer Ausarbeitung mit LaTeX (einschließlich Rahmen-Datei als Vorlage)
* Tips zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)


Weitere Auskünfte erteilt Mark Scharbrodt.


Mark Scharbrodt
Last modified: Thu Jul 12 16:24:32 CEST 2001