Optimal flow through the disordered lattice

被引：3

作者：

Aldous, David ^{[1
]}

机构：

[1] Univ Calif Berkeley, Berkeley, CA 94720 USA

来源：

ANNALS OF PROBABILITY | 2007年 / 35卷 / 02期

关键词：

concentration of measure; disordered lattice; first passage percolation; flow; local weak convergence; random network; routing;

D O I：

10.1214/009117906000000719

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Consider routing traffic on the N x N torus, simultaneously between all source-destination pairs, to minimize the cost Sigma 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 -> infinity 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.

引用

页码：397 / 438

页数：42

共 21 条

[1]

Ahuja RK, 1993, NETWORK FLOWS THEORY

[2]

Aldous D. J., 2006, ALEA-LAT AM J PROBAB, V1, P89

[3]

ALDOUS DJ, 2005, COST VOLUME RELATION

[4] Convergence to equilibrium of random Ising models in the Griffiths phase [J].