Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Sommersemester 2007

Thema: Das Traveling-Salesman-Problem

Termin: montags 14-16 Uhr

Beim Traveling-Salesman-Problem, einem klassischen Problem der Kombinatorischen Optimierung, besteht die Aufgabe darin, zu einer gegebenen Menge von Städten eine möglichst kurze Rundreise zu finden, bei der jede Stadt einmal besucht wird. Das Problem ist NP-schwer, aber es gibt einerseits für wichtige Spezialfälle ein polynomielles Approximationsschema, und andererseits lassen sich in der Praxis auch sehr große Instanzen effizient lösen.
Die Vorträge in diesem Seminar basieren auf ausgewählten Kapiteln des soeben erschienenen Buches "The Traveling Salesman Problem: A Computational Study" von D. L. Applegate, R. E. Bixby, V. Chvatal und W. J. Cook (Princeton University Press, 2007), sowie auf Originalarbeiten. Die Autoren des genannten Buches sind die weltweit führenden Experten für das Lösen großer Traveling-Salesman-Probleme.

Nr.	Datum	Name	Thema	Betreuung
1	2.4.	Mareike Mink	Kapitel 2: Applications, Kapitel 3: Dantzig, Fulkerson, and Johnson und Kapitel 4.1: Branch-and-Bound	Stephan Held
2	16.4.	Nina Merz	Kapitel 15: Tour finding	Stephan Held
3	23.4.	Markus Moll	Arora: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems	Jens Maßberg
4	30.4.	Tim Offermann	Christofides: Worst-case analysis of a new heuristic for the traveling salesman problem und Held und Karp: The traveling-salesman problem and minimum spanning trees	Dirk Müller
5	7.5.	Christian Neuen	Papadimitriou und Yannakakis: The traveling salesman problem with distances one and two	Jens Maßberg
6	21.5.	Alisa Maloglazova	Kapitel 5.3 - 5.7: Cutting Planes I	Markus Struzyna
7	4.6.	Thomas Schulte-Wülwer	Kapitel 5.8 - 5.10: Cutting Planes II und Kapitel 6.1 - 6.3: Subtour cuts	Markus Struzyna
8	11.6.	Ulrike Suhl	Kapitel 6.4, 6.5: Subtour cuts and PQ-trees	Ulrich Brenner
9	11.6. (16 Uhr!)	Alexander Sagrebin	Kaplan, Lewenstein, Shafrir und Sviridenko: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs	Jens Maßberg
10	18.6.	Adrian Bock	Kapitel 7: Cuts from blossoms and blocks	Ulrich Brenner
11	25.6.	Jesco Humpola	Fleischer, Letchford und Lodi: Polynomial-time separation of a superclass of simple comb inequalities	Dirk Müller
12	2.7.	Klaus Radke	Kapitel 10: Cut metamorphoses	Christian Schulte
13	9.7.	Dirk Ossenberg-Engels	Kapitel 11.1 - 11.4: Local cuts	Ulrich Brenner

Alle Teilnehmerinnen und Teilnehmer sollten die Kapitel 1, 4, 5.1 und 5.2 vor Beginn der Vorträge gelesen haben.

Voraussetzungen:

Vordiplom und mindestens eine Vorlesung (besser mehrere) aus dem Bereich der Diskreten Mathematik oder Mathematischen Optimierung.

Scheinkriterien:

Erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Dr. T. Nieberg,
Dr. U. Brenner