Minimization on Stochastic Matroids

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1990
Accession Number
ADA227413

Entities

People

  • Michael P. Bailey

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Business Administration
  • Classification
  • Computer Science
  • Inequalities
  • Markov Chains
  • Markov Processes
  • Mathematical Programming
  • North Carolina
  • Operations Research
  • Optimization
  • Parametric Analysis
  • Probability
  • Probability Distributions
  • Random Variables
  • Standards

Fields of Study

  • Mathematics

Readers

  • Exercise and Sports Science.
  • Mathematical Modeling and Probability Theory.
  • Statistical inference.