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. 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 a realistic military communications problem.