Premium
Maximum flow in networks with a small number of random arc capacities
Author(s) -
Somers J. E.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120304
Subject(s) - corollary , mathematics , random variable , expected value , flow (mathematics) , maximum flow problem , flow network , arc (geometry) , value (mathematics) , mathematical optimization , combinatorics , discrete mathematics , statistics , geometry
In a directed, capacitated network with single source and sink in which the capacities of some of the arcs are random variables, the max‐flow value is also a random variable. I propose a new approach to the problem of computing its distribution and expected value via a corollary of the max‐flow min‐cut theorem, and implement it explicitly for small numbers of random capacities. I consider the error obtained in estimating the expected max‐flow value by setting some of the random capacities equal to their means. When the flows are restructed by lower bounds, I give the probability of existence of a feasible flow.