121633
20180913054413.0
0302-9743
CONF
New approaches for virtual private network design
2005
2005
Conference Papers
Virtual private network design is the following NP-hard 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 traffic-matrices 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 2-commodity 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). © Springer-Verlag Berlin Heidelberg 2005.
Eisenbrand, Friedrich
183121
240331
Grandoni, Fabrizio
Oriolo, Gianpaolo
Skutella, Martin
1151 - 1162
Lecture Notes in Computer Science
3580
208381
n/a
http://infoscience.epfl.ch/record/121633/files/newVPN.pdf
DISOPT
252111
U11879
oai:infoscience.tind.io:121633
SB
conf
DISOPT-CONF-2005-005
05429422420/DISOPT
OTHER
PUBLISHED
CONF