Maximization on matroids with random weights
By: Michael P. Bailey
Contributors: Naval Postgraduate School (U.S.). Dept. of Operations Research
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1991
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 26
Subjects: Weighting functions; Optimization; Matroids; Markov processes
Other titles: NPS-OR-91-06.
Description: In this work we develop a method for analyzing maximum weight selections in matroids with      random element weights, especially exponentially distributed weights. We use the structure      of the matroid dual to transform matroid maximization into an equivalent minimization task.      We model sample paths of the greedy minimization scheme using a Markov process, and      thus solve the original maximization problem. The distribution of the weight of the optimal      basic element and moments are found, as well as the probability that a given basic element is      optimal. We also derive criticality indices for each ground set element, giving the probability      that an element is a member of the optimal solution. We give examples using spanning trees      and scheduling problems, each example being a new result in stochastic combinatorial      optimization.
Notes: Title from cover.

"NPS-OR-91-06."

"January 1991."

AD A233 978.

Includes bibliographical references (p. 22-23)

aq/aq cc:9116 01/20/98