DocumentCode :
3270553
Title :
Graph reductions to speed up importance sampling-based static reliability estimation
Author :
L´Ecuyer, Pierre ; Saggadi, Samira ; Tuffin, Bruno
Author_Institution :
DIRO, Univ. de Montreal, Montreal, QC, Canada
fYear :
2011
fDate :
11-14 Dec. 2011
Firstpage :
429
Lastpage :
438
Abstract :
We speed up the Monte Carlo simulation of static graph reliability models by adding graph reductions to zero-variance importance sampling (ZVIS) approximation techniques. ZVIS approximation samples the status of links sequentially, and at each step we check if series-parallel reductions can be performed. We present two variants of the algorithm and describe their respective advantages. We show that the method satisfies robustness properties as the reliability of links increases. We illustrate theoretically on small examples and numerically on large ones the gains that can be obtained, both in terms of variance and computational time.
Keywords :
Monte Carlo methods; graph theory; reliability theory; sampling methods; Monte Carlo simulation; graph reductions; importance sampling based static reliability estimation; series-parallel reductions; static graph reliability models; zero variance importance sampling approximation techniques; Approximation algorithms; Approximation methods; Joining processes; Merging; Monte Carlo methods; Reliability; Topology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Simulation Conference (WSC), Proceedings of the 2011 Winter
Conference_Location :
Phoenix, AZ
ISSN :
0891-7736
Print_ISBN :
978-1-4577-2108-3
Electronic_ISBN :
0891-7736
Type :
conf
DOI :
10.1109/WSC.2011.6147770
Filename :
6147770
Link To Document :
بازگشت