Approximation algorithms for multicast routings in a network with multi-sources
We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G = (V,E) with a vertex set V, an edge set E and an edge weight w(e) >= 0, e epsilon E. We are given a source set S epsilon V with a weight g(e) >= 0, e epsilon S, a terminal set M subset of V - S with a demand function q : M -> R(+), and a real number K > 0, where g(s) means the cost for opening a vertex s is an element of S as a source in a multicast tree. Then the CMMTR asks to find a subset S' subset of S, a partition {Z(1), Z(2),..., Z(l)) of M, and a set of subtrees T(1), T(2),..., T(l) of G such that, for each i, Sigma(l is an element of Zi) q(t) <= K and T(i) spans Z(i) boolean OR {s} for some s epsilon S'. The objective is to minimize the sum of the opening cost of S' and the constructing cost of (T(i)), i.e., Sigma(s epsilon S') g(s) + Sigma(l)(i)=1 w(T(i)), where w(T(i)) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2puFL + PST)-approximation algorithm to the CMMTR, where puFL and PST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)rho(UFL) + (4/3)rho(ST)) -approximation algorithm.
approximation algorithm facility location problem graph algorithm multicast routing problem network optimization tree cover