Optimization of Pearl‘s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem : A. Becker and D. Geiger
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 78 KB
- Volume
- 82
- Category
- Article
- ISSN
- 0004-3702
No coin nor oath required. For personal study only.
✦ Synopsis
Forthcoming Papers
A. Becker and D. Geiger, Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
We show how to find a small loop curser in a Bayesian network. Finding such a loop cutset is the first step in the method of conditioning for inference. Our algorithm for finding a loop cutset, called MGA, finds a loop cutset which is guaranteed in the worst case to contain less than twice the number of variables contained in a minimum loop cutset. The algorithm is based on a reduction to the weighted vertex feedback set problem and a new approximation of the latter problem. The complexity of MGA is O(NI + n logn) where m and n are the number of edges and vertices respectively. A greedy algorithm, called GA, for the weighted vertex feedback is also analyzed and bounds on its performance are given. We test MGA on randomly generated graphs and find that the average ratio between tbe number of instances associated with the algorithm's output and the number of instances associated with an optimum solution is 1.22 for the graphs tested.