Simple algorithms for Gilmore–Gomory's traveling salesman and related problems

Simple algorithms for Gilmore–Gomory's traveling salesman and related problems

0.00 Avg rating0 Votes
Article ID: iaor2008497
Country: United Kingdom
Volume: 6
Issue: 6
Start Page Number: 499
End Page Number: 520
Publication Date: Nov 2003
Journal: Journal of Scheduling
Authors:
Keywords: scheduling, combinatorial optimization
Abstract:

We reconsider the version of the traveling salesman problem (TSP) first studied in a well-known paper by Gilmore and Gomory. In this, the distance between two cities A and B is an integrable function of the x-coordinate of A and the y-coordinate of B. This problem finds important applications in machine scheduling, workforce planning, and combinatorial optimization. We solve this TSP variant by a O(n log n) algorithm considerably simpler than previously known algorithms. The new algorithm demonstrates and exploits the structure of an optimal solution, and recreates it using minimal storage space without the use of edge interchanges.

Reviews

Required fields are marked *. Your email address will not be published.