Summary: 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 \in V\) and a set \(M \subseteq V - {s}\) of terminals with a nonnegative demand \(q(v), v \in M\), we wish to find a collection \({\mathcal T}=\{T_{1},T_{2},\ldots,T_{\ell}\}\) 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 \(\kappa > 0\). Let \(\lambda > 0\) denote a bulk capacity of an edge, and each edge \(e \in E\) has an installation cost \(w(e) \geq 0\) per bulk capacity; each edge \(e\) is allowed to have capacity \(k \lambda \) 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 \(\alpha + \beta q^{\prime}\) amount of capacity for the total demand \(q^{\prime}\) that passes through edge \(e\) along \(T _{i }\) and prescribed constants \(\alpha ,\beta \geq 0\), where \(\alpha \) means a fixed amount used to separate the inside of the routing \(T _{i }\) from the outside while term \(\beta q^{\prime}\) means the net capacity proportional to \(q^{\prime}\). The objective of GCTR is to find a collection \({\mathcal 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[ \lambda/(\alpha+\beta \kappa)] /\lfloor \lambda/(\alpha+\beta \kappa)\rfloor +\rho_{\text{ST}})\)-approximable if \(\lambda \geq \alpha + \beta \kappa \) holds, where \(\rho_{\text{ST}}\) is any approximation ratio achievable for the Steiner tree problem.
For the entire collection see [Zbl 1139.68006].