×

Some results for cluster traveling salesperson problem. (English) Zbl 0945.90044

Summary: In this paper, we consider a generalization on the Travelling Salesperson Problem, called the Cluster Traveling Salesperson Problem (abbreviated CTSP). In CTSP, we are given a graph \(G=(V,E)\) and a partition of \(V:V_1,\dots,V_k\) (the ‘clusters’); the goal is to find an optimum (i.e. shortest) tour which visits at least one city in each cluster. We will show that CTSP with triangle inequality is at least as hard to approximate as Minimum Set Cover. We also give an algorithm that solves \(k\)-CSTP in \(O(2^{3k}\cdot|V|^2)\) time, where \(k\) denotes the number of clusters.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite