Approximation to the Minimum Cost Edge Installation Problem

作者：Morsy Ehab^*; Nagamochi Hiroshi

来源：IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2010, E93A(4): 778-786.

DOI：10.1587/transfun.E93.A.778

• approximation algorithm
• graph algorithm
• routing problem
• network optimization

We consider the minimum cost edge installation problem (MCEI) in a graph G = (V, E) with edge weight w(e) >= 0. e is an element of E We are given a vertex s is an element of V designated as a sink, an edge capacity lambda > 0. and a source set S subset of V with demand q(v) is an element of |0,lambda|, v is an element of S For each edge e is an element of E. we are allowed to install an integer number h(e) of copies of e MCEI asks to send demand q(v) from each source v is an element of S along a single path P-v to the sink without splitting the demand of any source v is an element of S For each edge e is an element of E. a set of such paths can pass through a single copy of e in C as long as the total demand along the paths does not exceed the edge capacity lambda The objective is to find a set P = {P-v | v is an element of S} of paths of G that minimizes the installing cost Sigma(eCE) h(e)w(e) In this paper. we propose a (15/8 + rho(ST))-approximation algorithm to MCEI. where rho(SI) is any approximation ratio achievable tor the Steiner tree problem

• 出版日期2010-4