Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor2002482
Country: United States
Volume: 28
Issue: 4
Start Page Number: 422
End Page Number: 437
Publication Date: Dec 2000
Journal: Algorithmica
Authors: , , ,
Keywords: game theory
Abstract:

Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V1, ..., Vk. The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.

Reviews

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