Constant access systems
Subtitle: a general framework for greedy optimization on stochastic networks
By: Michael P. Bailey
Contributors: Naval Postgraduate School (U.S.). Dept. of Operations Research
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1989
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 33
Subjects: STOCHASTIC PROCESSES; NETWORKS
Other titles: NPS-55-89-02.
Description: 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.
Notes: Cover title.

"NPS-55-89-02."

"March 1989."

AD A207-525.

Includes bibliographical references (p. 32-32)

aq/aq cc:9116 03/26/97.