Optimal flow through the disordered lattice

DOI10.1214/009117906000000719MaRDI QIDQ2371944zbMATH OpenOpenAlexFDO

Authors David Aldous

Publication date 9 July 2007

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0511694

Mathematics Subject Classification ID

Processes in random environments (60K37) Stochastic network models in operations research (90B15)

Abstract: Consider routing traffic on the N x N torus, simultaneously between all source-destination pairs, to minimize the cost $su{m}_{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 $Noinfty$ 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.

Recommendations

• The localization properties of a random steady flow on a lattice
• Hydrodynamic limit of a disordered lattice gas
• Disordering asymptotics in the discrete approximation of an Arratia flow
• Dynamics of disordered quantum systems using flow equations
• Stochastic transport on flexible lattice under limited resources
• Cost-volume relationship for flows through a disordered network
• Flows on a cubic lattice
• Lattice flows in networks

Cites work

• A SHORT PROOF OF THE HARRIS–KESTEN THEOREM
• Bulk transport properties and exponent inequalities for random resistor and flow networks
• Convergence to equilibrium of random Ising models in the Griffiths phase.
• Cost-volume relationship for flows through a disordered network
• Critical behavior for maximal flows on the cubic lattice
• First-passage percolation, network flows and electrical resistances
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 2034359 (Why is no real title available?)
• scientific article; zbMATH DE number 2042288 (Why is no real title available?)
• scientific article; zbMATH DE number 2070282 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Network flows. Theory, algorithms, and applications.
• Percolating paths through random points
• Probability theory of classical Euclidean optimization problems
• Sharp thresholds of graph properties, and the k-sat problem
• Surfaces with minimal random weights and maximal flows: a higher dimensional version of first-passage percolation
• The cavity method at zero temperature
• The critical probability of bond percolation on the square lattice equals 1/2

Cited in

(4)

• Uniform multicommodity flow through the complete graph with random edge-capacities
• Cost-volume relationship for flows through a disordered network
• Uniform multicommodity flows in the hypercube with random edge‐capacities
• Asymptotic behavior of Aldous' gossip process

This page was built for publication: Optimal flow through the disordered lattice

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