Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 02261

The Travelling Salesman Problem

( Jun 23 – Jun 28, 2002 )

Please use the following short url to reference this page:



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.

  • David L. Applegate (AT&T Labs Research - Florham Park, US)
  • Egon Balas (Carnegie Mellon University, US)
  • Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
  • Robert E. Bixby (Rice University - Houston, US) [dblp]
  • Luciana Buriol (State University of Campinas, BR)
  • Harald Büsching (AGFA Deutschland - Köln, DE)
  • Vasek Chvátal (Rutgers University - Piscataway, US)
  • Peter I. Cowling (University of Bradford, GB) [dblp]
  • Willem de Paepe (TU Eindhoven, NL)
  • Vladimir Deineko (University of Warwick, GB)
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Michelangelo Grigni (Emory University, US) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • Keld Helsgaun (Roskilde University, DK)
  • Cor Hurkens (TU Eindhoven, NL)
  • David S. Johnson (AT&T Labs Research - Florham Park, US) [dblp]
  • Michael Jünger (Universität Köln, DE) [dblp]
  • Walter Kern (University of Twente, NL)
  • Ralf Keuthen (BTexact Technologies - Martlesham, GB)
  • Bernhard Korte (Universität Bonn, DE)
  • Jan Karel Lenstra (CWI - Amsterdam, NL)
  • Thomas M. Liebling (EPFL - Lausanne, CH)
  • Maarten Lipmann (TU Eindhoven, NL)
  • Andrea Lodi (University of Bologna, IT) [dblp]
  • Catherine C. McGeoch (Amherst College, US) [dblp]
  • Lyle A. McGeoch (Amherst College, US)
  • Denis Naddef (CSI Laboratoire - Grenoble, FR)
  • George Nemhauser (Georgia Institute of Technology, US)
  • David Neto (Altera Corp. - Toronto, CA)
  • Chris N. Potts (University of Southampton, GB)
  • Gerhard Reinelt (Universität Heidelberg, DE)
  • Jorge Riera-Ledesma (University of Tenerife - La Laguna, ES)
  • Giovanni Rinaldi (IASI-CNR - Roma, IT)
  • André Rohe (Sun Microsystems - Berlin, DE)
  • Juan Jose Salazar (University of Tenerife - La Laguna, ES)
  • Neil Simonetti (Bryn Athyn College, US)
  • J. Michael Steele (University of Pennsylvania, US)
  • Leen Stougie (TU Eindhoven, NL) [dblp]
  • Chris Walshaw (University of Greenwich, GB)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Anders Yeo (Royal Holloway University of London, GB) [dblp]
  • Martin Zachariasen (University of Copenhagen, DK)