An improved approximation algorithm for capacitated multicast routings in networks

Let G=(V,E) be a connected graph such that each edge e∈E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S⊆V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z1,Z2,…,Zℓ} of S and a set {T1,T2,…,Tℓ} of trees of G such that Zi consists of at most k terminals and each Ti spans Zi∪{s}. The objective is to minimize , where w(Ti) denotes the sum of weights of all edges in Ti. In this paper, we propose a (3/2+(4/3)ρ)-approximation algorithm to the CMTR, where ρ is the best achievable approximation ratio for the Steiner tree problem.