Eisenbrand, Friedrich and Grandoni, Fabrizio and Oriolo, Gianpaolo and Skutella, Martin (2007) New Approaches for Virtual Private Network Design. SIAM Journal of Computing, 37 (3). pp. 706721. ISSN 00975397

Text
EGOS05icalp.pdf  Accepted Version Download (208kB)  Preview 
Abstract
Virtual private network design is the following NPhard problem. We are given a communication network, represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid trafficmatrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often illusive. The main contributions of this paper are as follows: Using Hu’s 2commodity flow theorem, we provide a new lower bound on the cost of an optimum solution. Using this lower bound we reanalyze a simple routing scheme which has been described in the literature many times and provide a considerably stronger upper bound on its approximation ratio. We present a new randomized approximation algorithm for which, in contrast to earlier approaches from the literature, the resulting solution does not have tree structure. Finally we show that a combination of our new algorithm with the simple routing scheme yields a randomized algorithm with expected performance ratio 3.55 for virtual private network design. This is a considerable improvement of the previously best known approximation results (5.55 STOC’03, 4.74 SODA’05).
Item Type:  Scientific journal article, Newspaper article or Magazine article 

Subjects:  Computer sciences 
Depositing User:  Fabrizio Grandoni 
Date Deposited:  14 Mar 2014 09:08 
Last Modified:  24 May 2016 06:00 
URI:  http://repository.supsi.ch/id/eprint/4513 
Actions (login required)
View Item 