Traveling salesman problem under categorization

Traveling salesman problem under categorization

0.00 Avg rating0 Votes
Article ID: iaor19931197
Country: Netherlands
Volume: 12
Issue: 2
Start Page Number: 89
End Page Number: 95
Publication Date: Aug 1992
Journal: Operations Research Letters
Authors:
Abstract:

The paper introduces two new classes of traveling salesman problems (TSP1 and TSP2) which subsume the classical traveling salesman problem and the bottleneck traveling salesman problem. It is shown that these problems are strongly NP-complete on Halin graphs even though their extreme cases (i.e. traveling salesman problem and bottleneck traveling salesman problem) are solvable in polynomial time on such graphs. It is also shown that TSP2 is solvable in polynomial time on Halin graphs if an associated parameter p is fixed, but TSP1 still remains NP-complete. For TSP2, a polynomial time (for fixed p) heuristic is suggested which produces a solution whose objective function value is no worse than twice that of the optimal solution whenever the underlying graph is complete, undirected and edge weights satisfy the triangle inequality.

Reviews

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