Constant access systems: a general framework for greedy optimization on stochastic networks
Bailey, Michael P.
MetadataShow full item record
We consider network optimization problems in which the weights of the edges are random variables. We develop conditions on the combinatorial structure of the problem which guarantee that the objective function value is a first passage time in an appropriately constructed Markov process. The arc weights must be exponentially distributed, the method of solution of the deterministic problem must be greedy in a general sense, and the accumulation of objective function value during the greedy procedure must occur at a constant rate. We call these structures constant access systems after the third property. Examples of constant access systems include the shortest path system, time until disconnection in a network of failing components, and some bottleneck optimization problems. For each system, we give the distribution of the objective function, the distribution of the solution of the problem, and the probability that a given arc is a member of the optimal solution. We also provide easily implementable formulae for the moments of these quantities. Keywords: Stochastic networks, Stochastic optimization
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
NPS Report NumberNPS-55-89-02
Showing items related by title, author, creator and subject.
Bailey, Michael Page (Operations Research Society of America, 1992);We consider network optimization problems in which the weights of the edges are random variables. We develop conditions on the combinatorial structure of the problem which guarantee that the objective function value is a ...
DeWolfe, Dean D. (1986);Selective Reenlistment Bonuses (SRBs) are offered to improve retention in designated military occupational specialties (MOSs) for specified years-of- service intervals (zones). The amount of the bonus is set by assigning ...
Bailey, Michael P. (Monterey, California. Naval Postgraduate School, 1991-01); NPS-OR-91-06In 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 ...