This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Aldous, D. J. Search for Related Content

Cost–Volume Relationship for Flows Through a Disordered Network

Department of Statistics, University of California, Berkeley, California 94720
aldous{at}stat.berkeley.edu

In a network where the cost of flow across an edge is nonlinear in the volume of flow, and where sources and destinations are uniform, one can consider the relationship between total volume of flow through the network and the minimum cost of any flow with given volume. Under a simple probability model (locally tree-like directed network, independent cost–volume functions for different edges) we show how to compute the minimum cost in the infinite-size limit. The argument uses a probabilistic reformulation of the cavity method from statistical physics and is not rigorous as presented here. The methodology seems potentially useful for many problems concerning flows on this class of random networks. Making arguments rigorous is a challenging open problem.

Key Words: capacitated network; cavity method; first passage percolation; network flow; probability model
History: Received: February 1, 2005; revision received: March 1, 2008;