Optimal flow through the disordered lattice

Abstract

Consider routing traffic on the N x N torus, simultaneously between all source-destination pairs, to minimize the cost ${\sum }_{e}c(e)f^2(e)$, where f(e) is the volume of flow across edge e and the c(e) form an i.i.d. random environment. We prove existence of a rescaled $N\to \infty$ limit constant for minimum cost, by comparison with an appropriate analogous problem about minimum-cost flows across a M x M subsquare of the lattice.

Published at http://dx.doi.org/10.1214/009117906000000719 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• The cavity method at zero temperature
• A short proof of the Harris-Kesten Theorem

Cited by in corpus (2)

• Invariant matchings of exponential tail on coin flips in ${\mathbb{Z}}^d$
• Asymptotic behavior of Aldous' gossip process