doi:10.1007/978-3-642-03685-9_25
ISI:000269953900025
Rothvoß, Thomas
Sanità, Laura
On the Complexity of the Asymmetric VPN Problem
Berlin, Springer
http://cui.unige.ch/tcs/random-approx/2009/index.php
http://infoscience.epfl.ch/record/138778/files/vpn.pdf
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.
2009-06-12T18:15:04Z
http://infoscience.epfl.ch/record/138778
http://infoscience.epfl.ch/record/138778
Text