On the complexity of the asymmetric VPN problem

Thomas Rothvoß; Laura Sanità

doi:10.1007/978-3-642-03685-9_25

On the complexity of the asymmetric VPN problem

Thomas Rothvoß, Laura Sanità

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Citations (SciVal)

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 language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages	326-338
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-03685-9_25
Publication status	Published - 2009
Externally published	Yes
Event	12th 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 2009 → 23 Aug 2009

Publication series

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

Conference

Conference	12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Country/Territory	United States
City	Berkeley, CA
Period	21/08/09 → 23/08/09

Access to Document

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

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

Rothvoß, Thomas ; Sanità, Laura. / On the complexity of the asymmetric VPN problem. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. pp. 326-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{431c58b1846d4846a85baa33ba103999,

title = "On the complexity of the asymmetric VPN problem",

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.",

author = "Thomas Rothvo{\ss} and Laura Sanit{\`a}",

year = "2009",

doi = "10.1007/978-3-642-03685-9_25",

language = "English",

isbn = "3642036848",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "326--338",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 ; Conference date: 21-08-2009 Through 23-08-2009",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5687 LNCS, pp. 326-338, 12th 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, 21/08/09. https://doi.org/10.1007/978-3-642-03685-9_25

On the complexity of the asymmetric VPN problem. / Rothvoß, Thomas; Sanità, Laura.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings. 2009. p. 326-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 -

Rothvoß T, Sanità L. 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. 2009. p. 326-338. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03685-9_25

On the complexity of the asymmetric VPN problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this