• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Principled network reliability approximation: A counting-based approach.
Roger Paredes, Leonardo Duenas-Osorio, Kuldeep S. Meel and Moshe Y. Vardi.
Journal of Reliability Engineering and System Safety(RESS), November 2019.
As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is indispensable to support investment and decision making. However, network reliability problems are known to be #P-complete, a computational complexity class largely believed to be intractable. The computational intractability of network reliability motivates our quest for reliable approximations. Based on their theoretical foundations, available methods can be grouped as follows: (i) exact or bounds, (ii) guarantee-less sampling, and (iii) probably approximately correct (PAC). Group (i) is well regarded due to its useful byproducts, but it does not scale in practice. Group (ii) scales well and verifies desirable properties, such as the bounded relative error, but it lacks error guarantees. Group (iii) is of great interest when precision and scalability are required, as it harbors computationally feasible approximation schemes with PAC-guarantees. We give a comprehensive review of classical methods before introducing modern techniques and our developments. We introduce K-RelNet, an extended counting-based estimation method that delivers PAC-guarantees for the K-terminal reliability problem. Then, we test methods' performance using various benchmark systems. We highlight the range of application of algorithms and provide the foundation for future resilience engineering as it increasingly necessitates methods for uncertainty quantification in complex systems.
@article{PDMV19b,
author={
Paredes, Roger and Duenas-Osorio, Leonardo and Meel, Kuldeep S. and Vardi,
Moshe Y.
},
title={
Principled network reliability approximation: A counting-based approach.
},
journal=RESS,
bib2html_pubtype={Journal},
month=nov,
year={2019},
bib2html_dl_pdf={../Papers/ress.pdf},
bib2html_rescat={Counting},
abstract={
As engineered systems expand, become more interdependent, and operate in
real-time, reliability
assessment is indispensable to support investment and decision making.
However, network reliability problems
are known to be #P-complete, a computational complexity class largely
believed to be intractable. The computational
intractability of network reliability motivates our quest for reliable
approximations. Based on their theoretical
foundations, available methods can be grouped as follows: (i) exact or
bounds, (ii) guarantee-less sampling, and (iii)
probably approximately correct (PAC). Group (i) is well regarded due to its
useful byproducts, but it does not scale in
practice. Group (ii) scales well and verifies desirable properties, such as
the bounded relative error, but it lacks
error guarantees. Group (iii) is of great interest when precision and
scalability are required, as it harbors computationally
feasible approximation schemes with PAC-guarantees. We give a comprehensive
review of classical methods before introducing
modern techniques and our developments. We introduce K-RelNet, an extended
counting-based estimation method that delivers
PAC-guarantees for the K-terminal reliability problem. Then, we test
methods' performance using various benchmark systems.
We highlight the range of application of algorithms and provide the
foundation for
future resilience engineering as it increasingly necessitates methods for
uncertainty quantification in complex systems.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21