Buy this book
![Loading indicator](/images/ajax-loader-bar.gif)
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.
Buy this book
![Loading indicator](/images/ajax-loader-bar.gif)
Previews available in: English
Subjects
Weighting functions, Optimization, Matroids, Markov processesEdition | Availability |
---|---|
1
Maximization on matroids with random weights
1991, Naval Postgraduate School, Available from National Technical Information Service
in English
|
aaaa
|
Book Details
Edition 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
The Physical Object
ID Numbers
Community Reviews (0)
Feedback?July 24, 2014 | Created by ImportBot | import new book |