zbMATH — the first resource for mathematics

Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and realiability. (English) Zbl 0609.90093
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.

90C27 Combinatorial optimization
90C15 Stochastic programming
90B25 Reliability, availability, maintenance, inspection in operations research
90B10 Deterministic network models in operations research
90B35 Deterministic scheduling theory in operations research
Full Text: DOI