The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract)
| dc.creator | Fiorini, Samuel | |
| dc.creator | Oriolo, Gianpaolo | |
| dc.creator | Sanità, Laura | |
| dc.creator | Theis, Dirk Oliver | |
| dc.date | 2008-12-12 | |
| dc.date.accessioned | 2026-07-07T12:12:25Z | |
| dc.date.available | 2026-07-07T12:12:25Z | |
| dc.description | 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. | |
| dc.description | Oberwolfach abstract | |
| dc.identifier | https://arxiv.org/abs/0812.2355 | |
| dc.identifier | http://arxiv.org/abs/0812.2355 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/210539 | |
| dc.subject | Optimization and Control | |
| dc.subject | 90B18, 68M10 | |
| dc.title | The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract) | |
| dc.type | text |