Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-001 (March 21, 2008)

Approximating the Generalized Capacitated Tree-routing
by Ehab Morsy and Hiroshi Nagamochi

pdf File

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 ${\cal 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