State space partition algorithms for stochastic systems with applications to minimum spanning trees
✍ Scribed by Alexopoulos, Christos; Jacobson, Jay A.
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 210 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
We investigated state space partition methods for computing probability measures related to the operation of stochastic systems and present new theoretical results concerning their efficiency. These methods iteratively partition the system state space, producing at each step progressively tighter bounds that can be used for constructing simple and efficient Monte Carlo routines for estimating the probabilities of interest. We apply our findings to the evaluation of measures related to minimum spanning trees in graphs whose edges have independent discrete random weights. Specifically, we seek to compute the distribution of the weight of a minimum spanning tree and the probability that a given edge belongs to a minimum spanning tree. Both of these unsolved problems are shown to be #P-hard. The algorithms for the minimum spanning tree problems are immediately applicable to other matroid problems with randomly weighted elements.