Approximation algorithms for network design in non-uniform fault models

• 成果类型: Article; Early Access
• 署名作者: Chekuri, Chandra; Jain, Rhea
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02298-x
• 发表日期: 2025-12-01
• 关键词: Bulk-robust network design; Approximation algorithms; non-uniform faults; Flexible graph connectivity

摘要

The Survivable Network Design problem (SNDP) is a well-studied problem, (partly) motivated by the design of networks that are robust to faults under the assumption that any subset of edges up to a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. We consider three models: the flexible graph connectivity model (Adjiashvili, D.: Fault-tolerant shortest paths - beyond the uniform failure model (unpublished).) (Adjiashvili, D. et al. in Math. Program. 192(1-2), 409-441 (2022)) (Boyd, S. et al. in Math. Program. pp. 1-24 (2023)) which was our initial motivation, the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61-77. Schloss Dagstuhl - Leibniz-Zentrum f & uuml;r Informatik, Dagstuhl, Germany (2015)) (Adjiashvili, D. et al,: in Math. Program. 149(1-2), 361-390 (2015)) and the relative survivable network design model (Dinitz, M. et al.: in Algorithms and Techniques (APPROX/RANDOM 2022), Leibniz International Proceedings in Informatics (LIPIcs), 245, pp. 41:1-41:19. Schloss Dagstuhl - Leibniz-Zentrum f & uuml;r Informatik, Dagstuhl, Germany (2022)) (Dinitz, M. et al.: in Algorithms, pp. 190-204. Springer Nature Switzerland, Cham (2023)). While SNDP admits a 2-approximation (Jain, K.: in Combinatorica 21(1), 39-60 (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 the robustness parameters are fixed constants, we consider two important special cases, namely the single pair case and the global connectivity case. For both these, we obtain constant factor approximations in several parameter ranges of interest. These are based on an augmentation framework and via decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second set of results are poly-logarithmic approximations for the bulk-robust model (Adjiashvili, D. in Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 40, pp. 61-77. Schloss Dagstuhl - Leibniz-Zentrum f & uuml;r Informatik, Dagstuhl, Germany (2015)) 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. The results are obtained via two algorithmic approaches and they have different tradeoffs in terms of the approximation ratio and generality.