Technical Report CS0428

TR#:CS0428
Class:CS
Title: A CORRECTION ALGORITHM FOR TOKEN PASSING SEQUENCES IN MOBILE COMMUNICATION NETWORKS
Authors: Y.I. Gold and S. Moran
PDFCS0428.pdf
Abstract: We present a distributed approximation algorithm for the Travelling Salesman Problem, that corrects an existing tour, rather than computing one "from scratch". Under certain circumstances the correction procedure is less costly than the "from scratch" procedure: the correctioll algorithm is suitable for dynamic graphs with slowly changing edge weights, and for which a Travelling Salesman tour (optimal or approximate) was previously computed and is "deteriorating" with time due to the weight changes. The algorithm can be used to "refresh" the lOur whenever it deteriorates beyond a given level, and thus, maintain a reasonabl~ average' lOur length at relatively low computation and communication costs. For a Euclidean graph with n nodes layed oui in a bounded area with diameter D, the maximal length of the tour produced by the algorithm is proportional to D\sqrt{n} ,like the maximal length of an optimal tour in that graph (the two differ by a factor of 2 at the worst case).

The algorithm was designed for the practical application of maintaining a short lOken-passing path (which means low scheduling overhead) in certain communication networks with mobile nodes.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1986/CS/CS0428), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion
admin