On the approximation of the generalized capacitated tree-routing problem

In this paper, we study the generalized capacitated tree-routing problem   (GCTR), which was introduced to unify the several known multicast problems in networks with edge/demand capacities. Let G=(V,E)G=(V,E) be a connected underlying graph with a bulk edge capacity λ>0λ>0 and an edge weight w(e)⩾0w(e)⩾0, e∈Ee∈E; we are allowed to construct a network on G   by installing any edge capacity keλkeλ with an integer ke⩾0ke⩾0 for each edge e∈Ee∈E, where the resulting network costs ∑e∈Ekew(e)∑e∈Ekew(e). Given a sink s∈Vs∈V, a set M⊆VM⊆V of terminals with a demand q(v)⩾0q(v)⩾0, v∈Mv∈M, and a demand capacity κ>0κ>0, we wish to construct the minimum cost network so that all the demands can be sent to s   along a suitable collection T={T1,T2,…,Tp}T={T1,T2,…,Tp} of trees rooted at s  , where the total demand collected by each tree TiTi is bounded from above by κ  , and the flow amount f(e)f(e) of TT that goes through each edge e   is bounded from above by the edge capacity keλkeλ. In this paper, f(e)f(e) is defined as ∑Ti∈T:e∈Ti[α+βqTi(e)] for prescribed constants α,β⩾0α,β⩾0, where qTi(e)qTi(e) denotes the total demand that passes through the edge e   along TiTi. The term α   means a fixed amount used to establish the routing TiTi by separating the inside of TiTi from the outside while the term βqTi(e)βqTi(e) means the net capacity proportional to the demand qTi(e)qTi(e). The objective of GCTR is to construct a minimum cost network that admits a collection TT of trees to send all demand to sink. It was left open to show whether GCTR with λ<α+βκλ<α+βκ is approximable by a constant factor or not. In this paper, we present a 13.037-approximation algorithm to GCTR for this case.