Solving a class of stochastic minimization problems

This work gives a methodology for analyzing a class of discrete minimization problems with random element weights. The minimum weight solution 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. The paper then presents two-sided bounds for matroids with NBUE distributed weights, as well as for weights with bounded positive hazard rates. It illustrates the present method using a realistic military communications problem.