TY - CPAPER
DO - 10.1007/978-3-642-03685-9_25
AB - We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (VPN) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2 OPT and that a tree solution of (expected) cost at most 49.84 OPT can be determined in polynomial time. Furthermore, we answer an outstanding open question about the complexity status of the so called balanced VPN problem by proving its NP-hardness.
T1 - On the Complexity of the Asymmetric VPN Problem
DA - 2009
AU - Rothvoß, Thomas
AU - Sanità, Laura
JF - 12th Intl. Workshop on Approximation Algorithms for Combinat
SP - 326-338
EP - 326-338
PB - Springer
PP - Berlin
ID - 138778
KW - Network design
KW - approximation algorithms
KW - NP-hardness
UR - http://cui.unige.ch/tcs/random-approx/2009/index.php
UR - http://infoscience.epfl.ch/record/138778/files/vpn.pdf
ER -