https://www.dagstuhl.de/02261

June 23 – 28 , 2002, Dagstuhl Seminar 02261

The Travelling Salesman Problem

Organizers

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

For support, please contact

Dagstuhl Service Team

Documents

List of Participants
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.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.