Constant Access Systems: A General Framework for Greedy Optimization on Stochastic Networks
Loading...
Authors
Bailey, Michael Page
Subjects
Networks/graphs, stochastic: networks with random arc lengths.
Networks/graphs
flow algonthms: stochastic flow networks. Networks/graphs
Networks/graphs
flow algonthms: stochastic flow networks. Networks/graphs
Advisors
Date of Issue
1992
Date
Publisher
Operations Research Society of America
Language
Abstract
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 continuous time Markov chain. The arc weights must be distributed exponentially, 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, the longest path system, the 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 formulas for the moments of each optimal objective function value, as well as criticality indices for each arc.
Type
Article
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Naval Postgraduate School Research Foundation
Funder
Air Force Office of Scientific Research AFOSR 84-0140.
Format
15 p.
Citation
Bailey, Michael Page. "Constant access systems: a general framework for greedy optimization on stochastic networks." Operations research 40.3-supplement-2 (1992): S195-S209.
Distribution Statement
Rights
This 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.