Mathematics – Optimization and Control
Scientific paper
2008-12-12
Mathematics
Optimization and Control
Oberwolfach abstract
Scientific paper
The symmetric Virtual Private Network Design (VPND) problem is concerned with buying capacity on links (edges) in a communication network such that certain traffic demands can be met. We investigate a natural generalization of VPND where the cost per unit of capacity may decrease if a larger amount of capacity is reserved (economies of scale principle). The growth of the cost of capacity is modelled by a non-decreasing concave function $f$. We call the problem the concave symmetric Virtual Private Network Design (cVPND) problem. After showing that a generalization of the so-called Pyramidal Routing problem and hence also the cVPND have the so-called tree routing property, we study approximation algorithms for cVPND. For general $f$, using known results on the so-called Single Source Buy at Bulk problem by Grandoni and Italiano, we give a randomized 24.92-approximation algorithm.
Fiorini Samuel
Oriolo Gianpaolo
Sanità Laura
Theis Dirk Oliver
No associations
LandOfFree
The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-610169