Accession Number : ADA267494


Title :   State Space Partitioning Methods for Solving a Class of Stochastic Network Problems


Descriptive Note : Doctoral thesis,


Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH


Personal Author(s) : Jacobson, Jay A


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267494.pdf


Report Date : May 1993


Pagination or Media Count : 134


Abstract : This study focuses on state space partitioning techniques for computing measures related to the operation of stochastic systems. These methods iteratively decompose the system state space until the measure of interest has been determined. The information available in each iteration yields lower and upper bounds on this measure, and can be used to design efficient Monte Carlo estimation routines. We present here new theoretical results identifying strategies for significantly enhancing the performance of these algorithms. Using these results, we describe a generalized algorithm that can easily be tailored to address a variety of problems. We net use this algorithm to analyze two important models in the area of stochastic network optimization. The first concerns the probabilistic behavior of minimum spanning trees in graphs with discrete random arc weights. Specifically, we compute the probability distribution of the weight of a minimum spanning tree and the probability that a given arc is on a minimum spanning tree. Both of these problems are shown to be P-hard. The second model considers minimum cost flows in networks with discrete random arc costs and capacities


Descriptors :   *COMPUTATIONS , *STOCHASTIC PROCESSES , ALGORITHMS , PROBABILITY DISTRIBUTION FUNCTIONS , GRAPHS , THESES , MONTE CARLO METHOD , PROBLEM SOLVING , ITERATIONS , DECOMPOSITION , NETWORK FLOWS


Subject Categories : Statistics and Probability


Distribution Statement : APPROVED FOR PUBLIC RELEASE