On the Complexity of the Asymmetric VPN Problem

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.


Publié dans:
12th Intl. Workshop on Approximation Algorithms for Combinat, 326-338
Présenté à:
12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009
Année
2009
Publisher:
Berlin, Springer
Mots-clefs:
Laboratoires:




 Notice créée le 2009-06-12, modifiée le 2019-01-17

n/a:
Télécharger le documentPDF
Lien externe:
Télécharger le documentURL
Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)