### 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 | |

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 | United States |

City | Berkeley, CA |

Period | 21/08/09 → 23/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

*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