In this paper, we introduce the generalized capacitated tree-routing problem (GCTR), which is described as follows. Given a connected graph G = (V, E) with a sink s ∈ V and a set M C V - {s} of terminals with a nonnegative demand q(v), v ∈ M, we wish to find a collection T = {T_1, T_2,..., T_e} of trees rooted at s to send all the demands to s, where the total demand collected by each tree T_i is bounded from above by a demand capacity κ > 0. Let λ > 0 denote a bulk capacity of an edge, and each edge e ∈ E has an installation cost w(e) ≥ 0 per bulk capacity; each edge e is allowed to have capacity k λ for any integer k, which installation incurs cost kw(e). To establish a tree routing T_i, each edge e contained in T_i requires α + βq' amount of capacity for the total demand q that passes through edge e along T_i and prescribed constants a, β > 0, where a means a fixed amount used to separate the inside of the routing T_i from the outside while term βq' means the net capacity proportional to q'. The objective of GCTR is to find a collection T of trees that minimizes the total installation cost of edges. Then GCTR is a new generalization of the several known multicast problems in networks with edge/demand capacities. In this paper, we prove that GCTR is (2[λ//(α + βκ)]/[λ/(α + βκ)] +ρ_(ST))-approximable if λ ≥ α + βκ holds, where ρ_(ST) is any approximation ratio achievable for the Steiner tree problem.
展开▼
