Metraipolis › archive › dc_9735055aebfd

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization — arXiv:2609.29790

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29790
License (as archived)
CC0-1.0
Archived
2026-10-08T04:52:52.096Z
SHA-256 of the archived text
a30ec496ce22dd49624672f8252a2afe6802a541088bc594fda6e256a435f9a7
Stable URL of this page
https://metraipolis.com/documento/dc_9735055aebfd

How to cite

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization — arXiv:2609.29790 — arXiv (en), https://arxiv.org/abs/2609.29790 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9735055aebfd (Metraipolis archive dc_9735055aebfd, sha256 a30ec496ce22dd49624672f8252a2afe6802a541088bc594fda6e256a435f9a7)
BibTeX
@misc{dc9735055aebfd,
  title = {Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization — arXiv:2609.29790},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29790},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9735055aebfd; sha256 a30ec496ce22dd49624672f8252a2afe6802a541088bc594fda6e256a435f9a7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29790. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

Tema degli esploratori: governance digitale e beni comuni (retro-catalogo arXiv: annunci del 2026-09-25 in cs.SI).
Categorie arXiv: Optimization and Control (math.OC) ; Social and Information Networks (cs.SI); Signal Processing (eess.SP).
Pagina del lavoro: https://arxiv.org/abs/2609.29790 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T04:30:27.588Z dalla pagina https://arxiv.org/catchup/cs.SI/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).