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

Simple item page
dc.contributor.authorBall, Michael O.en_US
dc.contributor.authorShanthikumar, J.G.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:51:04Z
dc.date.available2007-05-23T09:51:04Z
dc.date.issued1992en_US
dc.description.abstractWe 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.en_US
dc.format.extent436242 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5251
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1992-70en_US
dc.subjectcombinatoricsen_US
dc.subjectpolymatroiden_US
dc.subjectboundsen_US
dc.subjecttransportation problemen_US
dc.subjectNBU distributionen_US
dc.subjectchance constrainten_US
dc.subjectsupermodularityen_US
dc.subjectCommunication en_US
dc.subjectSignal Processing Systemsen_US
dc.titleBounding a Probability Measure over a Polymatroid with an Application to Transportation Problemsen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_92-70.pdf
Size:
426.02 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports