  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.
