Minimization on Stochastic Matroids
Michael Page Bailey · 1990
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)