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: | Shier Douglas R., Jarvis James P. |
Keywords: | random graphs |
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.