https://www.dagstuhl.de/02261

23. – 28. Juni 2002, Dagstuhl-Seminar 02261

The Travelling Salesman Problem

Organisatoren

David S. Johnson (AT&T Labs Research – Florham Park, US)
Jan Karel Lenstra (CWI – Amsterdam, NL)
Gerhard J. Woeginger (TU Eindhoven, NL)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Teilnehmerliste
Dagstuhl-Seminar-Report 346

Summary

The Traveling Salesman Problem belongs to the most basic, most important, and most investigated problems in optimization and theoretical computer science: A salesman has to visit each city from a given set exactly once. In doing this, he starts from his home city, and in the very end he has to return again to this home city. He wants to visit the cities in such an order that the total of the distances traveled in his tour becomes as small as possible, since this will save him time and gas. The Traveling Salesman Problem (TSP) consists in identifying this shortest tour through the cities.

The TSP has many important applications in vehicle routing, VLSI design, production scheduling, cutting wallpaper, job sequencing, data clustering, curve reconstruction, etc etc etc. Research on the TSP has followed many different paths: There are studies of its computational complexity, of its approximability, of the complexity and approximability behavior of various of its special cases, there are many implementations e.g. via cutting planes, there are studies and comparisons of implementations, there are approaches via graph theory that study certain Hamiltonian structures etc. etc. etc.

The Dagstuhl seminar on the TSP brought together researchers from Theoretical Computer Science, Operations Research, Mathematical Programming, Discrete Applied Mathematics, and Combinatorics who discussed new developments and new progress made on the TSP during the last 15 years.

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.