Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities

We show how to obtain stochastic bounds for the strong stochastic ordering and the concave ordering of the maximal flow in a network where the capacities are non negative discrete random variables. While the deterministic problem is polynomial, the stochastic version with discrete random variables i...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2020-11, Vol.353, p.77-105
Main Authors: Echabbi, L., Fourneau, J.M., Gacem, O., Lotfi, H., Pekergin, N.
Format: Article
Language:English
Subjects:
Computer Science
Increasing convex ordering
Maximal flow
Modeling and Simulation
Random capacity
Stochastic ordering
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show how to obtain stochastic bounds for the strong stochastic ordering and the concave ordering of the maximal flow in a network where the capacities are non negative discrete random variables. While the deterministic problem is polynomial, the stochastic version with discrete random variables is NP-hard. The monotonicity of the Min-Cut problem for these stochastic orderings allows us to simplify the input distributions and obtain bounds on the results. Thus we obtain a tradeoff between the complexity of the computations and the precision of the bounds. We illustrate the approach with some examples.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2020.10.014