Approximating capacitated tree-routings in networks
Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M subset of V be a set of terminals with a demand function q : M -> R(+), kappa > 0 be a routing capacity, and lambda >= 1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition M = {Z(1), Z(2), ... , Z(l)} of M and a set tau = {T(1), T(2), ... , T(l)} of trees of G such that each T(i) contains Z(i) boolean OR {s} and satisfies Sigma(upsilon is an element of Zi) q(upsilon) <= kappa. A single copy of an edge e is an element of E can be shared by at most lambda trees in tau; any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M, T) that minimizes the total installing cost. In this paper, we propose a (2+rho(ST))-approximation algorithm to CTR, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.
approximation algorithm graph algorithm routing problems network optimization tree cover