Constant access systems: A general framework for greedy optimization on stochastic networks

The paper considers network optimization problems in which the weights of the edges are random variables. It develops 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. These structures are called 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. Each system is given 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. Easily implementable formulas for the moments of each optimal objective function value are also provided, as well as criticality indices for each arc.