Approximating the minmax rooted-subtree cover problem
Let G = (V, E) be a connected graph such that each edge e is an element of E and each vertex nu is an element of V are weighted by nonnegative reals w(e) and h(nu), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p subtrees T-1, T-2,..., T-p such that each T-i contains X-i boolean OR {r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in T-i and the weights of vertices in X-i. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p cycles C-1, C-2,..., C-P such that C-i contains X-i boolean OR {r} so as to minimize the maximum cost of the cycles, where the cost of C-i is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p + 1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p + 1))-approximation algorithm to the MRCC with a metric (G, w).
partition approximation algorithm graph algorithm subtree cover problem traveling salesman problem