Integrated Graph-Data Models for Survivable K-Edge-Connected Network Design: Optimization with Data-Driven Edge Capacities
Boletim da Sociedade Paranaense de Matemática · 28.10.2026 · 44 (14) · 1-17
DOI: 10.5269/bspm.85854 ↗Kurz gefasst
Fachartikel in der Zeitschrift Boletim da Sociedade Paranaense de Matemática, online erschienen am 28.10.2026. Verfasst von Suvarna Mohanrao Nade und 1 weiteren Autor:innen. Die Arbeit nennt 64 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This article studies the design of minimum cost networks that support $k$-edge-connectivity requirements uniformly, where edge capacities are not considered to be fixed parameters but as data. The classical minimum-cost $k$-edge-connected spanning subgraph (k-ECSS) problem is known to be NP-hard for $k \ge 2$ and has been widely studied in the context of approximation algorithms, with recent progresses which result in almost-linear-time LP-based $2$-approximation algorithms. This paper contributes three things. First, it presents an integrated modeling framework that unifies combinatorial survivability constraints \`a la $k$-edge-connectivity with data-driven edge capacity estimates along with uncertainty bounds obtained from graph neural network-based predictions. Second, it designs a computational-hardening mixed-integer optimization (MIO) model for survivable network design under uncertain learned capacities, with $k$-edge-connectedness and chance-constrained capacity, based on a cut-based formulation of $k$-connectivity. Third, it introduces a two-level algorithmic approach that integrates near-linear-time LP relaxation and sparsification methods for the k-ECSS core problem with scenario-based rounding and re-optimization ruled by learned capacity distributions. We complement our theoretical results by providing a hardness result and an approximation guarantee for the integrated problem under standard assumptions stating that it is still NP-complete while it does not admit any better approximation guarantees than the classical factor of two. However, the proposed method maintains the worst-case approximation factor yet supports adaptive capacity-aware design. We perform conceptual experiments over benchmark network topologies and synthetic traffic data to show that the optimal network design and spare-capacity allocation patterns change dramatically when using learned capacity distributions, resulting in designs that are more cost-efficient as well as robust while remaining algorithmically tractable.
Zitieren
APA
Nade, S. M., & Pathak, R. P. (2026). Integrated Graph-Data Models for Survivable K-Edge-Connected Network Design: Optimization with Data-Driven Edge Capacities. Boletim da Sociedade Paranaense de Matemática, 44(14), 1-17. https://doi.org/10.5269/bspm.85854
Vancouver
Nade SM, Pathak RP. Integrated Graph-Data Models for Survivable K-Edge-Connected Network Design: Optimization with Data-Driven Edge Capacities. Boletim da Sociedade Paranaense de Matemática. 2026;44(14):1-17. doi:10.5269/bspm.85854
BibTeX
@article{Nade2026,
author = {Nade, Suvarna Mohanrao and Pathak, Renu Praveen},
title = {Integrated Graph-Data Models for Survivable K-Edge-Connected Network Design: Optimization with Data-Driven Edge Capacities},
journal = {Boletim da Sociedade Paranaense de Matemática},
year = {2026},
volume = {44},
number = {14},
pages = {1--17},
doi = {10.5269/bspm.85854}
}
EUVIMED