Constant Access Systems: A General Framework for Greedy Optimization on Stochastic Networks

Michael Page Bailey
Additional contact information
Michael Page Bailey: U.S. Naval Postgraduate School, Monterey, California

Operations Research, 1992, vol. 40, issue 3-supplement-2, S195-S209

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.

Keywords: networks/graphs; flow algorithms: stochastic flow networks; networks/graphs; stochastic: networks with random arc lengths (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.S195 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:3-supplement-2:p:s195-s209

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().