Document Open Access Logo

Approximation Algorithms for Network Design in Non-Uniform Fault Models

Authors Chandra Chekuri, Rhea Jain

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.36.pdf
  • Filesize: 0.73 MB
  • 20 pages

Document Identifiers

Author Details

Chandra Chekuri
  • Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, IL, USA
Rhea Jain
  • Department of Computer Science, University of Illinois, Urbana-Champaign, Urbana, IL, USA

Funding

  • Chekuri, Chandra: Supported in part by NSF grants CCF-1910149 and CCF-1907937.
  • Jain, Rhea: Supported in part by NSF grant CCF-1907937.

Acknowledgements

We thank Qingyun Chen for clarifications on a proof in [Chen et al., 2022]. We thank Joseph Cheriyan for pointers and helpful comments on flexible graph connectivity. The initial impetus for our work on this topic came from [Boyd et al., 2023].

Cite AsGet BibTex

Chandra Chekuri and Rhea Jain. Approximation Algorithms for Network Design in Non-Uniform Fault Models. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.36

Abstract

Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the flexible graph connectivity model [Adjiashvili, 2013; Adjiashvili et al., 2020; Adjiashvili et al., 2022; Boyd et al., 2023], in which the edge set is partitioned into safe and unsafe edges. Given parameters p,q ≥ 1, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. We also discuss the bulk-robust model [Adjiashvili et al., 2015; Adjiashvili, 2015] and the relative survivable network design model [Dinitz et al., 2022]. While SNDP admits a 2-approximation [K. Jain, 2001], the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when p and q are fixed, we consider two special cases. For the s-t case we obtain an approximation ratio that depends only on p,q whenever p+q > pq/2 which includes (p,2) and (2,q) for all p,q ≥ 1. For the global connectivity case we obtain an O(q) approximation for (2,q), and an O(p) approximation for (p,2) and (p,3) for any p ≥ 1, and for (p,4) when p is even. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second result is a poly-logarithmic approximation for a generalization of the bulk-robust model when the "width" of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. We utilize a recent framework due to Chen et al. [Chen et al., 2022] that was designed for handling group connectivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • non-uniform faults
  • network design
  • approximation algorithm

Metrics

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

References

  1. David Adjiashvili. Fault-tolerant shortest paths - Beyond the uniform failure model, 2013. URL: https://doi.org/10.48550/arXiv.1301.6299.
  2. David Adjiashvili. Non-uniform robust network design in planar graphs. arXiv preprint, 2015. URL: https://arxiv.org/abs/1504.05009.
  3. David Adjiashvili, Felix Hommelsheim, and Moritz Mühlenthaler. Flexible graph connectivity. In International Conference on Integer Programming and Combinatorial Optimization, pages 13-26. Springer, 2020. Google Scholar
  4. David Adjiashvili, Felix Hommelsheim, and Moritz Mühlenthaler. Flexible graph connectivity. Mathematical Programming, 192(1):409-441, 2022. Google Scholar
  5. David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), volume 227 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SWAT.2022.5.
  6. David Adjiashvili, Sebastian Stiller, and Rico Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1):361-390, 2015. Google Scholar
  7. Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions, 2022. To appear in Proc. of ICALP 2023. URL: https://doi.org/10.48550/arXiv.2209.11209.
  8. Sylvia Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Mathematical Programming, pages 1-24, 2023. Preliminary version appeared in Proc. of FSTTCS 2021. URL: https://doi.org/10.1007/s10107-023-01961-5.
  9. R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 106-115. Society for Industrial and Applied Mathematics, 2000. Google Scholar
  10. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula. Approximability of capacitated network design. Algorithmica, 72(2):493-514, 2015. Google Scholar
  11. Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li, and Srivatsan Narayanan. Capacitated network design on undirected graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 71-80. Springer, 2013. Google Scholar
  12. Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna. Network design for vertex connectivity. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 167-176, 2008. Google Scholar
  13. Parinya Chalermsook, Fabrizio Grandoni, and Bundit Laekhanukit. On survivable set connectivity. In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 25-36. Society for Industrial and Applied Mathematics, 2015. URL: https://doi.org/10.1137/1.9781611973730.3.
  14. Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Transactions on Algorithms (TALG), 7(2):1-17, 2011. Google Scholar
  15. Chandra Chekuri and Rhea Jain. Approximating flexible graph connectivity via räcke tree based rounding, 2022. URL: https://doi.org/10.48550/arXiv.2211.08324.
  16. Chandra Chekuri and Rhea Jain. Augmentation based approximation algorithms for flexible network design, 2022. URL: https://doi.org/10.48550/arXiv.2209.12273.
  17. Qingyun Chen, Bundit Laekhanukit, Chao Liao, and Yuhao Zhang. Survivable network design revisited: Group-connectivity, 2022. Full version of paper in Proceedings of IEEE FOCS 2022. URL: https://doi.org/10.48550/arXiv.2204.13648.
  18. J. Chuzhoy and S. Khanna. An O(k³ log n)-approximation algorithm for vertex-connectivity survivable network design. Theory of Computing, 8:401-413, 2012. Google Scholar
  19. Michael Dinitz, Ama Koranteng, and Guy Kortsarz. Relative Survivable Network Design. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), volume 245 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1-41:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.41.
  20. Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 750-759, 1999. Google Scholar
  21. L. Fleischer, K. Jain, and D. P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838-867, 2006. Google Scholar
  22. András Frank. Kernel systems of directed graphs. Acta Sci. Math.(Szeged), 41(1-2):63-76, 1979. Google Scholar
  23. András Frank. Connections in combinatorial optimization, volume 38. Oxford University Press Oxford, 2011. Google Scholar
  24. Naveen Garg, Goran Konjevod, and Ramamoorthi Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. Journal of Algorithms, 37(1):66-84, 2000. Preliminary version in Proc. of ACM-SIAM SODA 1998. Google Scholar
  25. M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, E. Tardos, and D. P. Williamson. Improved approximation algorithms for network design problems. In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, pages 223-232, 1994. Google Scholar
  26. M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation algorithms for NP-hard problems, pages 144-191. PWS Publishing Company, Boston, MA, 1997. Google Scholar
  27. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O(log² klog log k)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 253-264, 2019. Google Scholar
  28. 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
  29. Anupam Gupta, Ravishankar Krishnaswamy, and Ramamoorthi Ravi. Tree embeddings for two-edge-connected network design. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1521-1538. SIAM, 2010. Google Scholar
  30. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, and Nan Wang. Integrality ratio for group steiner trees and directed steiner trees. SIAM Journal on Computing, 36(5):1494-1511, 2007. Google Scholar
  31. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 585-594, 2003. Google Scholar
  32. K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  33. Kamal Jain, Ion Măndoiu, Vijay V Vazirani, and David P Williamson. A primal-dual schema based approximation algorithm for the element connectivity problem. Journal of Algorithms, 45(1):1-15, 2002. Google Scholar
  34. David R Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Soda, volume 93, pages 21-30, 1993. Google Scholar
  35. David R Karger. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46-76, 2000. Google Scholar
  36. G. Kortsarz and Z. Nutov. Approximating minimum cost connectivity problems. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010. Google Scholar
  37. Z. Nutov. Approximating Steiner networks with node-weights. SIAM Journal on Computing, 39(7):3001-3022, 2010. Google Scholar
  38. Z. Nutov. Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Transactions on Algorithms (TALG), 9(1):1, 2012. Google Scholar
  39. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 255-264, New York, NY, USA, 2008. Association for Computing Machinery. URL: https://doi.org/10.1145/1374376.1374415.
  40. Gabriele Reich and Peter Widmayer. Beyond steiner’s problem: A vlsi oriented generalization. In International Workshop on Graph-theoretic Concepts in Computer Science, pages 196-210. Springer, 1989. Google Scholar
  41. D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica, 15(3):435-454, 1995. 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