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