138778
20190617200631.0
doi
10.1007/978-3-642-03685-9_25
ISI
000269953900025
CONF
On the Complexity of the Asymmetric VPN Problem
2009
Berlin
Springer
2009
Conference Papers
Lecture Notes in Computer Science
5687
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.
Network design
approximation algorithms
NP-hardness
243826
Rothvoß, Thomas
183730
243827
Sanità, Laura
190471
12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09)
UC Berkeley, USA
August 21-23, 2009
326-338
12th Intl. Workshop on Approximation Algorithms for Combinat
http://cui.unige.ch/tcs/random-approx/2009/index.php
URL
178299
http://infoscience.epfl.ch/record/138778/files/vpn.pdf
n/a
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:138778
conf
SB
GLOBAL_SET
183730
DISOPT-CONF-2009-006
EPFL
REVIEWED
PUBLISHED
CONF