Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"The salesman and the tourist," by H. Eugene Stanley and Sergey V. Buldyrev. Nature, 27 September 2001, pages 373-374.

The well-known traveling salesman problem involves finding the shortest possible route through a collection of cities. It is a global optimization problem. The traveling tourist problem, a local optimization problem, involves the path taken by a tourist who always visits the city nearest to his or her current location. No requirement is made on visiting a city only once or on having to visit every city. If no additional constraints are put on the path, a tourist will eventually be trapped in a route that oscillates between two cities-called a 2-cycle tourist trap. For this reason, researchers choose a nonnegative integer n, and add the constraint that the tourist cannot visit a city already visited in the previous n visits. In volume 87 of Physical Review Letters, Lima et al find that the distribution of the lengths of tourist trap cycles follows a decreasing power law function. One application of the traveling tourist problem may be to birds which repeatedly visit the same sites on their migratory routes.

--- Mike Breen