Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability

In many classical combinatorial optimization problems, including critical and shortest paths, maximum flow, and network reliability, the introduction of uncertainty considerably complicates the calculation of system performance. In fact, in these contexts, computing system performance exactly can often be an impossible task. Therefore, obtaining (stochastic) bounds on the system's performance becomes an attractive and useful alternative. This paper studies several stochastic bounds that are applicable to these contexts and to a broader set of problems that can be described by the general combinatorial concepts of clutters and blocking clutters. We begin our discussion by defining these unifying concepts and illustrating their specialization in several problem contexts.