An improved approximation algorithm for capacitated multicast routings in networks
Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S subset of V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z(1), Z(2), . . . , Z(l)} of S and a set {T-1, T-2, . . . , T-l} of trees of G such that Z(i) consists of at most k terminals and each Ti spans Z(i) boolean OR {s}. The objective is to minimize Sigma(l)(i=1) w(T-i), where w(T-i) denotes the sum of weights of all edges in T-i. In this paper, we propose a (3/2 + (4/3)rho)-approximation algorithm to the CMTR, where rho is the best achievable approximation ratio for the Steiner tree problem. (C) 2007 Elsevier B.V. All rights reserved.
approximation algorithm graph algorithm multicast routing problem network optimization tree cover