138778
20190117210912.0
10.1007/978-3-642-03685-9_25
doi
000269953900025
ISI
CONF
On the Complexity of the Asymmetric VPN Problem
Berlin
2009
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
Rothvoß, Thomas
183730
243826
Sanità, Laura
190471
243827
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
URL
http://cui.unige.ch/tcs/random-approx/2009/index.php
n/a
178299
n/a
http://infoscience.epfl.ch/record/138778/files/vpn.pdf
DISOPT
252111
U11879
oai:infoscience.tind.io:138778
SB
GLOBAL_SET
conf
183730
DISOPT-CONF-2009-006
EPFL
PUBLISHED
REVIEWED
CONF