An improved algorithm for approximating the performance of stochastic flow networks

An improved algorithm for approximating the performance of stochastic flow networks

0.00 Avg rating0 Votes
Article ID: iaor19972062
Country: United States
Volume: 8
Issue: 4
Start Page Number: 355
End Page Number: 360
Publication Date: Oct 1996
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: random graphs
Abstract:

A problem encountered in the analysis of communication and other distribution systems is evaluating the performance of the system in meeting user demands with available resources. The authors consider the case in which user demands and available resources are only known stochastically and connecting links can operate at various levels. This situation can be modeled as a two-terminal stochastic network flow problem, in which each edge of the network assumes a finite number of values (corresponding to different capacity levels) with known probabilities. For each state of the network, the authors are interested in the maximum demand that can be met using the best allocation of resources. The approch used here to estimate the average unmet demand involves generating only ‘high leverage’ states of the system-states having high probability and/or high values of unmet demand. A new algorithm is proposed for generating such states in monotone order, either by probability or by unmet demand. Bounds on the performance of the network are investigated.

Reviews

Required fields are marked *. Your email address will not be published.