Accuracy vs. Complexity: the stochastic bound approach

We present an algorithmic technique based on stochastic ordering to obtain upper and lower bounding distributions for the results of some optimisation problems on discrete random variables which are hard to solve exactly due to the multiplicative increasing size of the distribution at each step. We illustrate the approach with the distribution of the completion time of a task graph.