Cost-volume relationship for flows through a disordered network

DOI10.1287/MOOR.1080.0327MaRDI QIDQ3168994zbMATH OpenOpenAlexFDO

Authors David Aldous

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0502346

zbMATH Keywords

capacitated networkcavity methodfirst passage percolationnetwork flowprobability model

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Stochastic network models in operations research (90B15)

Abstract: 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 $v$ of flow through the network and the minimum cost $c=Psi(v)$ of any flow with volume $v$. Under a simple probability model (locally tree-like directed network, independent cost-volume functions or different edges) we show how to compute $Psi(v)$ 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.

Recommendations

• Optimal flow through the disordered lattice
• scientific article; zbMATH DE number 3850794
• Infinite networks: Minimal cost flows
• scientific article; zbMATH DE number 1984104
• scientific article; zbMATH DE number 3845308

Cited in

(3)

• Uniform multicommodity flow through the complete graph with random edge-capacities
• Optimal flow through the disordered lattice
• A survey of max-type recursive distributional equations

This page was built for publication: Cost-volume relationship for flows through a disordered network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168994)