ISSN:
1432-0541
Keywords:
Key words. Traveling salesman problem, Approximation algorithms, Clustered traveling salesman.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 V 1 , . . ., V k . 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004530010045
Permalink