Article ID: | iaor19881286 |
Country: | United States |
Volume: | 14 |
Issue: | 2 |
Start Page Number: | 275 |
End Page Number: | 280 |
Publication Date: | May 1989 |
Journal: | Mathematics of Operations Research |
Authors: | Kern Walter |
Keywords: | graphs, probability |
The paper presents a general technique for obtaining bounds on the deviation of the optimal value of some stochastic combinatorial problems from their mean. As a particular application, it proves an exponential rate of convergence for the length of a shortest path through