TY - JOUR

T1 - From uncertainty to nonlinearity

T2 - Solving virtual private network via single-sink buy-at-bulk

AU - Grandoni, Fabrizio

AU - Rothvoß, Thomas

AU - Sanità, Laura

PY - 2011/5

Y1 - 2011/5

N2 - 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). In this paper we give the first constant factor approximation for concave VPN, and we improve the best-known approximation factor for linear VPN. Our approximation results build on a novel reduction, based on König's theorem, which allows us to turn uncertainty of traffic into nonlinearity of the objective function. This way, we are able to reduce linear VPN and concave VPN to the single-sink rent-or-buy problem (SROB) and the single-sink buy-at-bulk problem (SSBB), respectively. Using the machinery developed for the latter two problems plus additional ideas, we are able to improve the approximation ratio for VPN. Along the way we also obtain, among other results, an improved approximation algorithm for SSBB and a tighter bound on the gap between the costs of arbitrary solutions and tree solutions for VPN. Furthermore, solving an open problem, we show that VPN remains NP-hard even in the balanced case, where the sum of ingoing and outgoing traffic bounds is equal.

AB - 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). In this paper we give the first constant factor approximation for concave VPN, and we improve the best-known approximation factor for linear VPN. Our approximation results build on a novel reduction, based on König's theorem, which allows us to turn uncertainty of traffic into nonlinearity of the objective function. This way, we are able to reduce linear VPN and concave VPN to the single-sink rent-or-buy problem (SROB) and the single-sink buy-at-bulk problem (SSBB), respectively. Using the machinery developed for the latter two problems plus additional ideas, we are able to improve the approximation ratio for VPN. Along the way we also obtain, among other results, an improved approximation algorithm for SSBB and a tighter bound on the gap between the costs of arbitrary solutions and tree solutions for VPN. Furthermore, solving an open problem, we show that VPN remains NP-hard even in the balanced case, where the sum of ingoing and outgoing traffic bounds is equal.

KW - Approximation algorithms

KW - Buy-at-bulk

KW - Randomized algorithms

KW - Rent-or-buy

KW - Virtual private network

UR - http://www.scopus.com/inward/record.url?scp=79957719550&partnerID=8YFLogxK

U2 - 10.1287/moor.1110.0490

DO - 10.1287/moor.1110.0490

M3 - Article

AN - SCOPUS:79957719550

SN - 0364-765X

VL - 36

SP - 185

EP - 204

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 2

ER -