The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract)

Details The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract) The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract)

2008-12-12

arxiv.org/abs/0812.2355v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-610169