ISSN:
1432-0541
Keywords:
Round-robin token-passing
;
Mobile communication
;
Euclidean Traveling Salesman tours
;
Approximation algorithms
;
Incremental corrections
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We present a distributed approximation algorithm for the Traveling Salesman Problem (TSP) in networks that use a broadcast, multiaccess communication channel. The application for which the algorithm was originally designed is maintaining a short token-passing path (which means low scheduling overhead) in radio networks with mobile nodes. The algorithm is adaptive in the sense that it shifts gradually between performing a slight correction of an existing tour and recomputing one “from scratch.” It can thus be viewed as a generalization, or extension, of conventional TSP algorithms. The proposed algorithm guarantees the same worst-case tour length as the one guaranteed by any conventional “from scratch” algorithm, yet it is capable of taking advantage of certain node layouts (e.g., geographically clustered nodes) to reduce the cost of computing the path. The correction algorithm is suitable for dynamic graphs with slowly changing edge weights, and for which a Traveling Salesman tour (optimal or approximate) has previously been computed and is “deteriorating” with time due to the weight changes. The algorithm can be used to “refresh” the tour whenever it deteriorates beyond a given level, and thus maintain a reasonable average tour length at relatively low computation and communication costs. For a Euclidean graph withn nodes laid out in a bounded area with diameterD, the maximal length of the tour produced by the algorithm is proportional toD√n, like the maximal length of an optimal tour in that graph (the two differ by a factor of 2 at the worst case).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01553895
Permalink
