Grandoni, Fabrizio
Rothvoss, Thomas
Sanita, Laura
From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk
Mathematics Of Operations Research
Mathematics Of Operations Research
Mathematics Of Operations Research
Mathematics Of Operations Research
36
approximation algorithms
randomized algorithms
virtual private network
buy-at-bulk
rent-or-buy
Design
2011
2011
The virtual private network problem (VPN) models scenarios in which traffic is uncertain or rapidly changing. The goal is supporting at minimum cost a given family of traffic matrices, which are implicitly given by upper bounds on the ingoing and outgoing traffic at each node. Costs are classically defined by a linear function (linear VPN), but we consider here also the more general case of concave increasing costs (concave VPN).
0364-765X
Mathematics Of Operations Research
Journal Articles
10.1287/moor.1110.0490