Document Open Access Logo

Approximability of Robust Network Design: The Directed Case

Authors Yacine Al-Najjar, Walid Ben-Ameur, Jérémie Leguay

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.6.pdf
  • Filesize: 1.33 MB
  • 16 pages

Document Identifiers

Author Details

Yacine Al-Najjar
  • Huawei Technologies, Paris Research Center, France
  • Samovar, Telecom SudParis, Institut Polytechnique de Paris, France
Walid Ben-Ameur
  • Samovar, Telecom SudParis, Institut Polytechnique de Paris, France
Jérémie Leguay
  • Huawei Technologies, Paris Research Center, France

Cite AsGet BibTex

Yacine Al-Najjar, Walid Ben-Ameur, and Jérémie Leguay. Approximability of Robust Network Design: The Directed Case. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.6

Abstract

We consider robust network design problems where an uncertain traffic vector belonging to a polytope has to be dynamically routed to minimize either the network congestion or some linear reservation cost. We focus on the variant in which the underlying graph is directed. We prove that an O(√k) = O(n)-approximation can be obtained by solving the problem under static routing, where k is the number of commodities and n is the number of nodes. This improves previous results of Hajiaghayi et al. [SODA'2005] and matches the Ω(n) lower bound of Ene et al. [STOC'2016] and the Ω(√k) lower bound of Azar et al. [STOC'2003]. Finally, we introduce a slightly more general problem version where some flow restrictions can be added. We show that it cannot be approximated within a ratio of k^{c/(log log k)} (resp. n^{c/(log log n)}) for some constant c. Making use of a weaker complexity assumption, we prove that there is no approximation within a factor of 2^{log^{1- ε} k} (resp. 2^{log^{1- ε} n}) for any ε > 0.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Routing and network design problems
Keywords
  • Robust Optimization
  • Network Design
  • Approximation
  • Inapproximability
  • Competitive Ratio of Oblivious Routing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Y. Al-Najjar, W. Ben-Ameur, and J. Leguay. On the approximability of robust network design. Theoretical Computer Science, 860:41-50, 2021. Google Scholar
  2. D. Applegate and E. Cohen. Making intra-domain routing robust to changing and uncertain traffic demands: Understanding fundamental tradeoffs. In Proc. ACM SIGCOMM, 2003. Google Scholar
  3. Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. In Proc. ACM STOC, 2003. Google Scholar
  4. Y. Bartal and S. Leonardi. Ondashline routing in all-optical networks. Theoretical Computer Science, 221(1):19-39, 1999. Google Scholar
  5. W. Ben-Ameur. Between fully dynamic routing and robust stable routing. In International Workshop on Design and Reliable Communication Networks, 2007. Google Scholar
  6. W. Ben-Ameur and H. Kerivin. New economical virtual private networks. Commun. ACM, 46(6):69-73, June 2003. Google Scholar
  7. W. Ben-Ameur and H. Kerivin. Routing of uncertain traffic demands. Optimization and Engineering, 6(3):283-313, 2005. Google Scholar
  8. W. Ben-Ameur and M. Żotkiewicz. Robust routing and optimal partitioning of a traffic demand polytope. International Transactions in Operational Research, 18(3):307-333, 2011. Google Scholar
  9. W. Ben-Ameur and M. Żotkiewicz. Multipolar routing: where dynamic and static routing meet. Electronic Notes in Discrete Mathematics, 41:61-68, 2013. Google Scholar
  10. D. Bertsimas and V. Goyal. On the power and limitations of affine policies in two-stage adaptive optimization. Mathematical programming, 134(2):491-531, 2012. Google Scholar
  11. C. Chekuri. Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News, 38(3):106-129, September 2007. Google Scholar
  12. C. Chekuri, F.B. Shepherd, G. Oriolo, and M.G. Scutellá. Hardness of robust network design. Networks, 50(1):50-54, 2007. Google Scholar
  13. G. Claßen, A. M. C. A. Koster, M. Kutschka, and I. Tahiri. Robust metric inequalities for network loading under demand uncertainty. APJOR, 32(5), 2015. Google Scholar
  14. N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. van der Merive. A flexible model for resource management in virtual private networks. SIGCOMM Comput. Commun. Rev., 29(4):95-108, August 1999. Google Scholar
  15. F. Eisenbrand, F. Grandoni, G. Oriolo, and M. Skutella. New approaches for virtual private network design. SIAM Journal on Computing, 37(3), 2007. Google Scholar
  16. A. Ene, G. Miller, J. Pachocki, and A. Sidford. Routing under balance. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 598-611, New York, NY, USA, 2016. Association for Computing Machinery. Google Scholar
  17. J.A. Fingerhut, S. Suri, and J. S. Turner. Designing least-cost nonblocking broadband networks. Journal of Algorithms, 24(2):287-309, 1997. Google Scholar
  18. A. Frangioni, F. Pascali, and M. G. Scutellà. Static and dynamic routing under disjoint dominant extreme demands. Operations research letters, 39(1):36-39, 2011. Google Scholar
  19. N. Goyal, N. Olver, and F. Shepherd. Dynamic vs. oblivious routing in network design. In European Symposium on Algorithms, pages 277-288. Springer, 2009. Google Scholar
  20. N. Goyal, N. Olver, and F. B. Shepherd. The vpn conjecture is true. Journal of the ACM (JACM), 60(3):1-17, 2013. Google Scholar
  21. A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proc. ACM STOC, 2001. Google Scholar
  22. A. Gupta and J. Könemann. Approximation algorithms for network design: A survey. Surveys in Operations Research and Management Science, 16(1):3-20, 2011. Google Scholar
  23. M. Hajiaghayi, R. Kleinberg, and T. Leighton. Semi-oblivious routing: lower bounds. In Proceedings of ACM-SIAM symposium on Discrete algorithms, pages 929-938, 2007. Google Scholar
  24. M. T. Hajiaghayi, R. D. Kleinberg, H. Räcke, and T. Leighton. Oblivious routing on node-capacitated and directed graphs. ACM Trans. Algorithms, 3(4), November 2007. URL: https://doi.org/10.1145/1290672.1290688.
  25. C. Harrelson, K. Hildrum, and S. Rao. A polynomial-time tree decomposition to minimize congestion. In Proc. SPAA, 2003. Google Scholar
  26. I. Haviv and O. Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 469-477, 2007. Google Scholar
  27. P. Kumar, Y. Yuan, C. Yu, N. Foster, R. Kleinberg, P. Lapukhov, C. Lin Lim, and R. Soulé. Semi-oblivious traffic engineering: The road not taken. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 157-170. USENIX Association, 2018. Google Scholar
  28. H. P. L. Luna. Network planning problems in telecommunications. In Handbook of Optimization in Telecommunications, pages 213-240. Springer, 2006. Google Scholar
  29. B. M. Maggs, F. Meyer auf der Heide, B. Vöcking, and M. Westermann. Exploiting locality for data management in systems of limited bandwidth. In Proc. FOCS, 1997. Google Scholar
  30. S. Mattia. The robust network loading problem with dynamic routing. Comp. Opt. and Appl., 54(3):619-643, 2013. Google Scholar
  31. M. Minoux. Robust network optimization under polyhedral demand uncertainty is np-hard. Discrete Applied Mathematics, 158(5):597-603, 2010. Google Scholar
  32. N. Olver. Robust network design. PhD thesis, McGill University Library, 2010. Google Scholar
  33. N. Olver and F. B. Shepherd. Approximability of robust network design. Mathematics of Operations Research, 39(2):561-572, 2014. Google Scholar
  34. A. Ouorou and J.P. Vial. A model for robust capacity planning for telecommunications networks under demand uncertainty. In Workshop on Design and Reliable Communication Networks, 2007. Google Scholar
  35. M. Poss and C. Raack. Affine recourse for the robust network design problem: Between static and dynamic routing. Networks, 61(2):180-198, 2013. Google Scholar
  36. H. Räcke. Minimizing congestion in general networks. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 43-52, 2002. Google Scholar
  37. H. Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In 40th annual ACM symposium on Theory of Computing, pages 255-264, 2008. Google Scholar
  38. N. Wang, Kin H. Ho, G. Pavlou, and M. Howarth. An overview of routing optimization for internet traffic engineering. IEEE Communications Surveys & Tutorials, 10(1):36-56, 2008. Google Scholar
  39. M. Żotkiewicz and W. Ben-Ameur. More adaptive robust stable routing. In IEEE Global Telecommunications Conference, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact