On the Complexity of the Asymmetric VPN Problem

DOI10.1007/978-3-642-03685-9_25MaRDI QIDQ3638888zbMATH OpenOpenAlexFDO

Authors Thomas Rothvoß, Laura Sanità

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL http://cui.unige.ch/tcs/random-approx/2009/index.php

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• The VPN Problem with Concave Costs
• From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk
• The asymmetric VPN tree problem: polyhedral results and Branch-and-Cut
• Virtual private network design
• Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks

Cited in

(7)

• The asymmetric VPN tree problem: polyhedral results and Branch-and-Cut
• Network design with a discrete set of traffic matrices
• From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk
• The VPN Problem with Concave Costs
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Some results on V-ary asymmetric tries
• Experiments on virtual private network design with concave capacity costs

This page was built for publication: On the Complexity of the Asymmetric VPN Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638888)