.png){kind=icon}
返回
A random searching algorithm for efficiently solving the connectivity-oriented robust optimization problem on large-scale networked systems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2025.112924.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
通过整合部分链路使其无懈可击，在网络预期故障强度下将不会出现连通性降级。尽管现有的链路整合方法能够处理大规模网络，但它们的解决方案远非最优。现有解决方案中的冗余可通过由必要链路子集构成的纯图的连通性来量化，而现有方法将纯图连通性提升至远高于预期值。幸运的是，我们发现了一种特殊的链路割的超级集合，并证明了通过从现有解决方案中移除正确的链路集，可以在保持所需连通性的同时减少整合链路。为应对寻找最优超级集的高复杂性，我们找到了一种接近最优解且易于定位的超级集，显著减少了需要整合的链路数量，仅略微增加了预处理开销。实验表明，在大规模网络中，该算法可提供超过99.9%的保护效果，且在相同计算时间内相比现有高速算法可节省60%的开销。在最优算法可行的小规模网络中，相比最优结果的平均额外成本可控制在1%以内。因此，在确保准确性的同时，相比现有算法能进一步逼近最优解，显著降低基础设施整合的开销。
Keyword:
Connectivity
Disjoint cut collection
Pure graph
Link consolidation
Approximation method