TY - GEN

T1 - On the complexity of the asymmetric VPN problem

AU - Rothvoß, Thomas

AU - Sanità, Laura

PY - 2009

Y1 - 2009

N2 - We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network 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. For the case of linear cost we obtain a (2+ εR/S)-approximation algorithm for any fixed ε > 0, where S and R (R ≥ S) denote the outgoing and ingoing demand, respectively. Furthermore, we answer an outstanding open question about the complexity status of the so called balanced problem by proving its NP-hardness.

AB - We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network 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. For the case of linear cost we obtain a (2+ εR/S)-approximation algorithm for any fixed ε > 0, where S and R (R ≥ S) denote the outgoing and ingoing demand, respectively. Furthermore, we answer an outstanding open question about the complexity status of the so called balanced problem by proving its NP-hardness.

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

U2 - 10.1007/978-3-642-03685-9_25

DO - 10.1007/978-3-642-03685-9_25

M3 - Conference contribution

AN - SCOPUS:70350577213

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 326

EP - 338

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009

Y2 - 21 August 2009 through 23 August 2009

ER -