UC Berkeley

Consider routing traffic on the N × N torus, simultaneously between all source-destination pairs, to minimize the cost ∑ec(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 → ∞ limit constant for minimum cost, by comparison with an appropriate analogous problem about minimum-cost flows across a M × M subsquare of the lattice. © Institute of Mathematical Statistics, 2007.