Approximating Capacitated Tree-Routings in Networks
Ehab Morsy, Hiroshi Nagamochi · IPSJ SIG Notes · 2007
Let G=(V,E) be a connected graph such that each edge e?E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M?V be a set of terminals with a demand function q:M?R +, ?>0 be a routing capacity, and ??1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition ?={Z 1,Z 2,?,Z ? } of M and a set ${\mathcal{T}}=\{T_{1},T_{2},\ldots,T_{\ell}\}$ of trees of G such that each T i contains Z i ?{s} and satisfies $\sum_{v\in Z_{i}}q(v)\leq \kappa$ . A single copy of an edge e?E can be shared by at most ? trees in ${\mathcal{T}}$ ; 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 $({\mathcal{M}},{\mathcal{T}})$ that minimizes the total installing cost. In this paper, we propose a (2+? ST )-approximation algorithm to CTR, where ? ST is any approximation ratio achievable for the Steiner tree problem.