Maximization on matroids with random weights
Abstract
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
NPS Report Number
NPS-OR-91-06Related items
Showing items related by title, author, creator and subject.
-
Shape Control of Composite Material Plates using Piezoelectric Actuators
Elshafei, M.A.; Agrawal, B.N. (1997);This paper concerns the shape control of composite material plates using piezoelectric actuators. A finite element formulation is developed for modeling a laminated composite plate that has piezoelectric actuators and ... -
The impact of cognitive feedback on the performance of intelligence analysts
Krotow, Geraldine S. (Monterey, California. Naval Postgraduate School, 1992-03);Human judgement and the process of decision making have been studied in depth for the past century. More recent research has revealed that feedback is a primary element in the decision making process. Feedback has been ... -
Optimal Fire-Support Strategies
Taylor, James G. (Monterey, California. Naval Postgraduate School, 1976-02); NPS55TW76021Deterministic optimal control theory is used to study the structure of optimal fire-support policies for some time-sequential tactical allocation problems with combat described by Lanchester-type equations of warfare. ...