TY - GEN

T1 - Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem (Extended Abstract)

AU - Guttmann-Beck, Nili

AU - Hassin, Refael

AU - Khuller, Samir

AU - Raghavachari, Balaji

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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 (CTSP) 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.

AB - 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 (CTSP) 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.

UR - http://www.scopus.com/inward/record.url?scp=84887047650&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887047650&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-49382-2_2

DO - 10.1007/978-3-540-49382-2_2

M3 - Conference contribution

AN - SCOPUS:84887047650

SN - 3540653848

SN - 9783540653844

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 6

EP - 17

BT - Foundations of Software Technology and Theoretical Computer Science - 18th Conference, Proceedings

T2 - 18th Foundations of Software Technology and Theoretical Computer Science Conference, FST and TCS 1998

Y2 - 17 December 1998 through 19 December 1998

ER -