A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

摘要

Given an edge-weighted tree T and an integer p≥1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2-2/(p+1))-approximation algorithm which runs in O(p~(p-1)n~(p-1)) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p-1)!·n) time.