بحث
On the approximation of the generalized capacitated tree-routing Problem

EhabMorsy and Hiroshi Nagamochi
 

Abstract:

In this paper, we study the generalized capacitated tree-routing problem (GCTR), which wasintroduced to unify the several known multicast problems in networks with edge/demandcapacities. Let G = (V , E) be a connected underlying graph with a bulk edge capacity λ>0and anonnegative edge weight w(e), e E; we are allowed to construct a network on G byinstalling any edge capacity k(e)λ with anonnegative integer k(e) for each edge e E, where theresulting network costs . Given a sink s V, a set M V of terminals with a nonnegativedemand q(v), v M, and a demand capacity κ> 0, we wish to construct the minimumcost network so that all the demands can be sent to s along a suitable collection T ={T1, T2, . . . , T p } of trees rooted at s, where the total demand collected by each tree Tiis bounded from above by κ, and the flow amount f(e) of T that goes through eachedge e is bounded from above by the edge capacity k(e)λ. In this paper, f (e) is defined as [α +βqTi (e)] for prescribed nonnegative constants α,β, where qTi (e) denotes the totaldemand that passes through the edge e along Ti. The term α means a fixed amount usedto establish the routing Ti by separating the inside of Ti from the outside while the termβqTi (e) means the net capacity proportional to the demand qTi (e). The objective of GCTRis to construct a minimum cost network that admits a collection T of trees to send alldemand to sink. It was left open to show whether GCTR with λ<α + βκ is approximableby a constant factor or not. In this paper, we present a 13.037-approximation algorithm toGCTR for this case.






شارك برايك
مارايك في موقعنا الجديد