New approaches for virtual private network design

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)