Seminario Interdipartimentale di Algoritmica
 

Monday, January 17, 2005, 12:00 noon
An Improved Approximation Algorithm for Virtual Private Network Design
Fabrizio Grandoni
Università di Roma "La Sapienza"

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

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 talk 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).