On the complexity of the asymmetric VPN problem

Thomas Rothvoß, Laura Sanità

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages326-338
Number of pages13
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States
Duration: 21 Aug 200923 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5687 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
CountryUnited States
CityBerkeley, CA
Period21/08/0923/08/09

Fingerprint Dive into the research topics of 'On the complexity of the asymmetric VPN problem'. Together they form a unique fingerprint.

  • Cite this

    Rothvoß, T., & Sanità, L. (2009). On the complexity of the asymmetric VPN problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings (pp. 326-338). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS). https://doi.org/10.1007/978-3-642-03685-9_25