Balanced and Approximate Zero-Variance Recursive Estimators for the Static Communication Network Reliability Problem

Abstract : Exact evaluation of static network reliability parameters belongs to the NP-hard family and Monte Carlo simulation is therefore a relevant tool to provide their estimations. The first goal of this paper is to review a Recursive Variance Reduction (RVR) estimator which approaches the unreliability by recursively reducing the graph from the random choice of the first working link on selected cuts. We show that the method does not verify the bounded relative error (BRE) property as reliability of individual links goes to one, i.e., that the estimator is not robust in general to high reliability of links. We then propose to use the decomposition ideas of the RVR estimator in conjunction with the Importance Sampling technique. Two new estimators are presented: the first one, called Balanced Recursive Decomposition estimator, chooses the first working link on cuts uniformly, while the second, called Zero-Variance Approximation Recursive Decomposition estimator, tries to mimic the estimator with variance zero for this technique. We show that in both cases BRE property is verified and, moreover, that a vanishing relative error (VRE) property can be obtained for the Zero-Variance Approximation RVR under specific sufficient conditions. A numerical illustration of the power of the methods is provided on several benchmark networks.
Type de document :
Article dans une revue
ACM Transactions on Modeling and Computer Simulation, Association for Computing Machinery, 2015, 25 (1), pp.19
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00908567
Contributeur : Bruno Tuffin <>
Soumis le : lundi 25 novembre 2013 - 08:42:28
Dernière modification le : mercredi 11 avril 2018 - 02:01:22
Document(s) archivé(s) le : mercredi 26 février 2014 - 04:23:49

Fichier

RVRERB-vTOMACS-v10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00908567, version 1

Citation

Héctor Cancela, Mohamed El Khadiri, Gerardo Rubino, Bruno Tuffin. Balanced and Approximate Zero-Variance Recursive Estimators for the Static Communication Network Reliability Problem. ACM Transactions on Modeling and Computer Simulation, Association for Computing Machinery, 2015, 25 (1), pp.19. 〈hal-00908567〉

Partager

Métriques

Consultations de la notice

700

Téléchargements de fichiers

191