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à

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

10 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Approximation, Randomization, and Combinatorial Optimization
Subtitel	Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pagina's	326-338
Aantal pagina's	13
DOI's	https://doi.org/10.1007/978-3-642-03685-9_25
Status	Gepubliceerd - 2009
Extern gepubliceerd	Ja
Evenement	12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, Verenigde Staten van Amerika Duur: 21 aug. 2009 → 23 aug. 2009

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5687 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
Land/Regio	Verenigde Staten van Amerika
Stad	Berkeley, CA
Periode	21/08/09 → 23/08/09

Toegang tot document

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

Andere bestanden en links

Link to publication in Scopus

Citeer dit

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 (blz. 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. blz. 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, blz. 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, Verenigde Staten van Amerika, 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. blz. 326-338 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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. blz. 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

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit