Bounding a Probability Measure over a Polymatroid with an Application to Transportation Problems

Abstract

We are given a set of supply nodes, a set of demand nodes and a set of arcs between certain supply/demand pairs, which indicate if the supply node can serve as a source for the demand node. The level of the supply available at each supply node and the amount demanded by each demand node are independent random variables. We derive an upper bound on the probability that the random demand can be met by the random supply under the assumption that the supply levels have new better than used (NBU) distribution functions. The functional form of the bound is the product of the probabilities that each demand node, viewed independently, can be feasibly satisfied. In order to prove this result we first prove another result concerning polymatroids. This result gives a lower bound on the probability that a random vector is the member of the polymatroid.