2008/12/12 by Samuel Fiorini, Gianpaolo Oriolo, Fiorini, Samuel +5
Computer Science · Mathematics · #68M10 #90B18 #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #math.OC #msc:68M10 #msc:90B18
paper · pdf · doi:10.48550/arxiv.0812.2355
Oberwolfach abstract
arxiv created 2008/12/12 · openalex publication_date 2008/12/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.