The Traveling Salesman Problem and Its Variations

The traveling salesman problem (TSP) i perhap s s the most well known combinatorial optimization problem. The book "The Travehng Sales man Problem: A guided tour of combinatorial optimization" edited by Lawler, Lenstra, Rinoo Ka y n and Shmoys provides the state of the art description of the topi u cp to 1985. Since then, several significant devel opments have taken place in the are ofa combinatorial optimization in general and the traveling salesman problem in particular. This warrants the need fo a r n updated book W . e discussed this matter with many distinguished colleagues. These consultations culminated in the project of compiling a new book on the TSP. Enthusiastic support from the re search community provide u d s with the courage and motivation to take up this challenging task. The pattern and style of this new book closely resemble thos of ites predecessor [548]. In addition to standard an d more traditional topics, we also cover domination analysis of approximation algorithms and some important variations of the TSP. The purpose of the book is to serve as a self-contained reference source which updates the book by Lawler et. al [548]. W believ e e that the book can also be used for specialized graduate and senior undergraduate courses an researc d h projects.