Approximation algorithms with constant ratio for general cluster routing problems

Due to their ubiquity and extensive applications, graph routing problems have been widely studied in the fields of operations research, computer science and engineering. An important example of a routing problem is the traveling salesman problem. In this paper, we consider two variants of the general cluster routing problem. In these variants, we are given a complete undirected graph $$G=(V,E)$$ G = ( V , E ) with a metric cost function c and a partition $$V=C_{1}\cup C_{2}\cdots \cup C_{k}$$ V = C 1 ∪ C 2 ⋯ ∪ C k of the vertex set. For a given subset $$V^{'}$$ V ′ of V and subset $$E^{'}$$ E ′ of E, the task is to find a walk T with minimum cost such that it visits each vertex in $$V^{\prime }$$ V ′ exactly once and covers each edge in $$E^{\prime }$$ E ′ at least once. Besides, for every $$i\in [k]$$ i ∈ [ k ] , all the vertices in $$T\cap C_i$$ T ∩ C i are required to be visited consecutively in T. We design two combinatorial approximation algorithms with ratios 21/11 and 2.75 for the two variants, respectively; both ratios match the approximation ratios for the corresponding variants of the cluster traveling salesman problem, a special case of general cluster routing problem.