An approximation algorithm for the clustered path travelling salesman problem

In this paper, we consider the clustered path travelling salesman problem. In this problem, we are given a complete graph $$G=(V,E)$$ G = ( V , E ) with an edge weight function w satisfying the triangle inequality. In addition, the vertex set V is partitioned into clusters $$V_1,\ldots ,V_k$$ V 1 , … , V k and s, t are two given vertices of G with $$s\in V_1$$ s ∈ V 1 and $$t\in V_k$$ t ∈ V k . The objective of the problem is to find a minimum Hamiltonian path of G from s to t, where all vertices of each cluster are visited consecutively. In this paper, we deal with the case that the start-vertex and the end-vertex of the path on each cluster are both specified, and for it we provide a polynomial-time approximation algorithm.