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

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.