Minimization on Stochastic Matroids
Loading...
Authors
Bailey, Michael P.
Subjects
Stochastic matroid; Stochastic spanning tree; NBUE distributions
Advisors
Date of Issue
1990-07
Date
1990-07
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
This work gives a methodology for analyzing matroids with random element weights, with emphasis placed on independent, exponentially distributed element weights. The minimum weight basic element in such a structure is shown to be an absorbing state in a Markov chain, while the distribution of weight of the minimum weight element is shown to be of phase-type. We then present two sided bounds for matroids with NBUE distributed weights, as well as for weights with bounded positive hazard rates. We illustrate our method using the transversal matroid to solve stochastic assignment problems. (Author) (kr)
Type
Technical Report
Description
Series/Report No
Department
Operations Research
Identifiers
NPS Report Number
NPS-55-90-14
Sponsors
Naval Postgraduate School Research Council.
Funder
0&MN, Direct Funding
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.