Consider routing traffic on the N×N torus, simultaneously between all source-destination pairs, to minimize the cost ∑ec(e)f2(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.
Publié le : 2007-03-14
Classification:
Concentration of measure,
disordered lattice,
first passage percolation,
flow,
local weak convergence,
random network,
routing,
90B15,
60K37
@article{1175287750,
author = {Aldous, David},
title = {Optimal flow through the disordered lattice},
journal = {Ann. Probab.},
volume = {35},
number = {1},
year = {2007},
pages = { 397-438},
language = {en},
url = {http://dml.mathdoc.fr/item/1175287750}
}
Aldous, David. Optimal flow through the disordered lattice. Ann. Probab., Tome 35 (2007) no. 1, pp. 397-438. http://gdmltest.u-ga.fr/item/1175287750/