بحث
Approximating capacitated tree-routings in networks

EhabMorsy and Hiroshi Nagamochi
 

Abstract

Let G=(V,E) be a connected graph such that each edge e in E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M subset of V be a set of terminals with a demand function q:MR +, k>0 be a routing capacity, and λ≥1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition M={Z 1,Z 2,…,Z l } of M and a set T={T1,T2,…,Tl} of trees of G such that each T i contains Z i and s and satisfies . A single copy of an edge eE can be shared by at most λ trees in T; any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M,T) that minimizes the total installing cost. In this paper, we propose a (2+p )-approximation algorithm to CTR, where p is any approximation ratio achievable for the Steiner tree problem.






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