An Approximation Algorithm for the (Metric) Clustered Path Traveling Salesman Problem
摘要
We consider the (metric) clustered path traveling salesman problem. In this problem, we are given a complete graph \(G=(V,E)\) along with a nonnegative edge cost function satisfying the triangle inequality, where V is partitioned into disjoint subsets \(V_1,\ldots ,V_k\) called clusters and \(s\in V_1,t\in V_k\) are two given vertices. The objective of the problem is to find a Hamiltonian path of G with minimum cost from s to t, satisfying that all vertices in each cluster are visited consecutively by this path. In this paper, we consider the problem in the case where endpoints of the subpath induced by the path on each cluster are both specified and a 2-approximation algorithm is given.