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)?0 w ( e ) ? 0 , e?E e ? E ; we are allowed to construct a network on G  by installing any edge capacity ke? k e ? with an integer ke?0 k e ? 0 for each edge e?E e ? E , where the resulting network costs ?e?Ekew(e) ? e ? E k e w ( e ) . Given a sink s?V s ? V , a set M?V M ? V of terminals with a demand q(v)?0 q ( v ) ? 0 , v?M v ? 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 = { T 1 , T 2 ,  , T p } of trees rooted at s , where the total demand collected by each tree Ti T i is bounded from above by ? , and the flow amount f(e) f ( e ) of T T that goes through each edge e  is bounded from above by the edge capacity ke? k e ? . In this paper, f(e) f ( e ) is defined as ? T i ? T : e ? T i [ ? + ? q T i ( e ) ] for prescribed constants ?,??0 ? , ? ? 0 , where qTi(e) q T i ( e ) denotes the total demand that passes through the edge e  along Ti T i . The term ?  means a fixed amount used to establish the routing Ti T i by separating the inside of Ti T i from the outside while the term ?qTi(e) ? q T i ( e ) means the net capacity proportional to the demand qTi(e) q T i ( e ) . The objective of GCTR is to construct a minimum cost network that admits a collection T T 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.
approximation algorithm graph algorithm routing problems network optimization tree cover