An improved approximation algorithm for virtual private network design

Virtual private network design deals with the reservation of capacities in a network, such that the nodes can share communication. Each node in the network has associated upper bounds on the amount of flow that it can send to the network and receive from the network respectively. The problem then is to reserve capacities at minimum cost and to compute paths between every pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. In this paper we present a simple 4.74-approximation algorithm for virtual private network design. The previous best approximation algorithm for this problem achieves a ratio of 5.55 (Gupta, Kumar, and Roughgarden STOC'03).


Published in:
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 928 - 932
Year:
2005
Laboratories:




 Record created 2008-05-13, last modified 2018-03-17

n/a:
Download fulltext
GZ

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)