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

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-l,...,V-k. The clustered traveling salesman pr oblem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutiv ely. Since this problem is a generalization of the traveling salesman probl em, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.