Grandoni, FabrizioRothvoss, ThomasSanita, Laura2011-12-162011-12-162011-12-16201110.1287/moor.1110.0490https://infoscience.epfl.ch/handle/20.500.14299/74086WOS:000290904300001The 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).approximation algorithmsrandomized algorithmsvirtual private networkbuy-at-bulkrent-or-buyDesigntext::journal::journal article::research article