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 MitarbeitProf. Dr. B. Korte,
Prof. Dr. J. Vygen,
Dr. T. Nieberg,
Dr. U. Brenner