LIPIcs.ESA.2017.19.pdf
- Filesize: 0.58 MB
- 12 pages
Document
Exploring the Tractability of the Capped Hose Model
Authors
-
Part of:
Volume:
25th Annual European Symposium on Algorithms (ESA 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-09-01
Cite As Get BibTex
Thomas Bosman and Neil Olver. Exploring the Tractability of the Capped Hose Model. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.19
Abstract
Robust network design concerns the design of networks to support uncertain or varying traffic patterns. An especially important case is the VPN problem, where the total traffic emanating from any node is bounded, but there are no further constraints on the traffic pattern. Recently, Fréchette et al. [INFOCOM, 2013] studied a generalization of the VPN problem where in addition to these so-called hose constraints, there are individual upper bounds on the demands between pairs of nodes. They motivate their model, give some theoretical results, and propose a heuristic algorithm that performs well on real-world instances. Our theoretical understanding of this model is limited; it is APX-hard in general, but tractable when either the hose constraints or the individual demand bounds are redundant. In this work, we uncover further tractable cases of this model; our main result concerns the case where each terminal needs to communicate only with two others. Our algorithms all involve optimally embedding a certain auxiliary graph into the network, and have a connection to a heuristic suggested by Fréchette et al. for the capped hose model in general.
Subject Classification
Keywords
- robust network design
- VPN problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- A. Altın, E. Amaldi, P. Belotti, and M. C. Pınar. Provisioning virtual private networks under traffic uncertainty. Networks, 49(1):100-115, 2007. URL: http://dx.doi.org/10.1002/net.v49:1.
- Walid Ben-Ameur and Hervé Kerivin. New economical virtual private networks. Commun. ACM, 46(6):69-73, 2003. URL: http://dx.doi.org/10.1145/777313.777314.
- Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM (JACM), 60(1):6, 2013. URL: http://dx.doi.org/10.1145/1806689.1806769.
-
Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971.
- N. G. Duffield, Pawan Goyal, Albert Greenberg, Partho Mishra, K. K. Ramakrishnan, and Jacobus E. van der Merwe. A flexible model for resource management in virtual private networks. In Proc. SIGCOMM, pages 95-108, 1999. URL: http://dx.doi.org/10.1145/316188.316209.
-
Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, and Martin Skutella. New approaches for virtual private network design. SIAM J. Comput., 37(3):706-721, 2007.
- Friedrich Eisenbrand and Edda Happ. Provisioning a virtual private network under the presence of non-communicating groups. In Proc. CIAC, pages 105-114, 2006. URL: http://dx.doi.org/10.1007/11758471_13.
- J. A. Fingerhut, S. Suri, and J. S. Turner. Designing least-cost nonblocking broadband networks. J. Algorithms, 24(2):287-309, August 1997. URL: http://dx.doi.org/10.1006/jagm.1997.0866.
-
S. Fiorini, G. Oriolo, L. Sanità, and D. O. Theis. The VPN problem with concave costs. SIAM J. Discrete Math., 24(3):1080-1090, 2010.
- Alexandre Fréchette, F. Bruce Shepherd, Marina K. Thottan, and Peter J. Winzer. Shortest path versus multi-hub routing in networks with uncertain demand. In Proc. INFOCOM, pages 710-718, 2013. URL: http://dx.doi.org/10.1109/INFCOM.2013.6566857.
- Navin Goyal, Neil Olver, and F. Bruce Shepherd. The VPN Conjecture is true. J. ACM, 60(3):17:1-17:17, 2013. URL: http://dx.doi.org/10.1145/2487241.2487243.
- Fabrizio Grandoni, Volker Kaibel, Gianpaolo Oriolo, and Martin Skutella. A short proof of the VPN tree routing conjecture on ring networks. Oper. Res. Lett., 36(3):361-365, 2008. URL: http://dx.doi.org/10.1016/j.orl.2007.10.008.
- Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. From uncertainty to nonlinearity: Solving virtual private network via single-sink buy-at-bulk. Mathematics of Operations Research, 36(2):185-204, 2011. URL: http://dx.doi.org/10.1287/moor.1110.0490.
- Anupam Gupta, Amit Kumar, Martin Pál, and Tim Roughgarden. Approximation via cost sharing: Simpler and better approximation algorithms for network design. J. ACM, 54(3):11, 2007. URL: http://dx.doi.org/10.1145/1236457.1236458.
-
C. A. J. Hurkens, J. C. M. Keijsper, and L. Stougie. Virtual private network design: A proof of the tree routing conjecture on ring networks. SIAM J. Discrete Math., 21(2):482-503, 2007.
- Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, and Ravi Sundaram. Designing overlapping networks for publish-subscribe systems. In Proc. APPROX, pages 381-395, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.381.
- N. Olver and F. B. Shepherd. Approximability of robust network design. In Proc. SODA, pages 1097-1105, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.89.
- Neil Olver. A note on hierarchical hubbing for a generalization of the VPN problem. Oper. Res. Lett., 44(2):191-195, 2016. URL: http://dx.doi.org/10.1016/j.orl.2015.12.020.