EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Integrated Graph-Data Models for Survivable K-Edge-Connected Network Design: Optimization with Data-Driven Edge Capacities

Suvarna Mohanrao Nade, Renu Praveen Pathak

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →