On the Complexity of the Asymmetric VPN ProblemReportar como inadecuado




On the Complexity of the Asymmetric VPN Problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Presented at: 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009 Published in: 12th Intl. Workshop on Approximation Algorithms for Combinat, p. 326-338 Series: Lecture Notes in Computer Science 5687 Berlin: Springer, 2009

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.

Keywords: Network design ; approximation algorithms ; NP-hardness Reference DISOPT-CONF-2009-006doi:10.1007/978-3-642-03685-9_25View record in Web of Science





Autor: Rothvoß, Thomas; Sanità, Laura

Fuente: https://infoscience.epfl.ch/record/138778?ln=en







Documentos relacionados