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!
cited_by
cites cdi_FETCH-LOGICAL-c332t-71e116a84beae4f7d78d253817b74a96bc34fc5232c835f0014cfe23330fad813
container_end_page 105
container_issue
container_start_page 77
container_title Electronic notes in theoretical computer science
container_volume 353
creator Echabbi, L.
Fourneau, J.M.
Gacem, O.
Lotfi, H.
Pekergin, N.
description 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.
doi_str_mv 10.1016/j.entcs.2020.10.014
format article
fullrecord <record><control><sourceid>hal_cross</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_04345108v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S1571066120300906</els_id><sourcerecordid>oai_HAL_hal_04345108v1</sourcerecordid><originalsourceid>FETCH-LOGICAL-c332t-71e116a84beae4f7d78d253817b74a96bc34fc5232c835f0014cfe23330fad813</originalsourceid><addsrcrecordid>eNp9kDlPAzEQhS0EEiHwC2jcUuziaw8KihAIQQpE4qgtxx5rHZI1sk0C_55dghAV1Yye3jfHQ-iUkpwSWp4vc2iTjjkjrFdyQsUeGtCiohkpS7r_pz9ERzEuCeE1rcoBmj8lrxsVk9P4yr-3JmLrA04N4Hv1gScrv8WuxQo_QNr68Iq3LjX42kUdIAF-VK3xazxWb0q75CAeowOrVhFOfuoQvUxunsfTbDa_vRuPZpnmnKWsokBpqWqxAAXCVqaqDSv6mxaVUBflQnNhdcE40zUvLOke0hYY55xYZWrKh-hsN7dRK_kW3FqFT-mVk9PRTPYaEVwUlNSb3st3Xh18jAHsL0CJ7POTS_mdn-zz68VuXUdd7ijo3tg4CDJqB60G4wLoJI13__JfYLB4sg</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities</title><source>BACON - Elsevier - GLOBAL_SCIENCEDIRECT-OPENACCESS</source><creator>Echabbi, L. ; Fourneau, J.M. ; Gacem, O. ; Lotfi, H. ; Pekergin, N.</creator><creatorcontrib>Echabbi, L. ; Fourneau, J.M. ; Gacem, O. ; Lotfi, H. ; Pekergin, N.</creatorcontrib><description>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.</description><identifier>ISSN: 1571-0661</identifier><identifier>EISSN: 1571-0661</identifier><identifier>DOI: 10.1016/j.entcs.2020.10.014</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Computer Science ; Increasing convex ordering ; Maximal flow ; Modeling and Simulation ; Random capacity ; Stochastic ordering</subject><ispartof>Electronic notes in theoretical computer science, 2020-11, Vol.353, p.77-105</ispartof><rights>2020 The Author(s)</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c332t-71e116a84beae4f7d78d253817b74a96bc34fc5232c835f0014cfe23330fad813</cites><orcidid>0000-0003-3386-7658</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://hal.science/hal-04345108$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Echabbi, L.</creatorcontrib><creatorcontrib>Fourneau, J.M.</creatorcontrib><creatorcontrib>Gacem, O.</creatorcontrib><creatorcontrib>Lotfi, H.</creatorcontrib><creatorcontrib>Pekergin, N.</creatorcontrib><title>Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities</title><title>Electronic notes in theoretical computer science</title><description>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.</description><subject>Computer Science</subject><subject>Increasing convex ordering</subject><subject>Maximal flow</subject><subject>Modeling and Simulation</subject><subject>Random capacity</subject><subject>Stochastic ordering</subject><issn>1571-0661</issn><issn>1571-0661</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp9kDlPAzEQhS0EEiHwC2jcUuziaw8KihAIQQpE4qgtxx5rHZI1sk0C_55dghAV1Yye3jfHQ-iUkpwSWp4vc2iTjjkjrFdyQsUeGtCiohkpS7r_pz9ERzEuCeE1rcoBmj8lrxsVk9P4yr-3JmLrA04N4Hv1gScrv8WuxQo_QNr68Iq3LjX42kUdIAF-VK3xazxWb0q75CAeowOrVhFOfuoQvUxunsfTbDa_vRuPZpnmnKWsokBpqWqxAAXCVqaqDSv6mxaVUBflQnNhdcE40zUvLOke0hYY55xYZWrKh-hsN7dRK_kW3FqFT-mVk9PRTPYaEVwUlNSb3st3Xh18jAHsL0CJ7POTS_mdn-zz68VuXUdd7ijo3tg4CDJqB60G4wLoJI13__JfYLB4sg</recordid><startdate>20201101</startdate><enddate>20201101</enddate><creator>Echabbi, L.</creator><creator>Fourneau, J.M.</creator><creator>Gacem, O.</creator><creator>Lotfi, H.</creator><creator>Pekergin, N.</creator><general>Elsevier B.V</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>1XC</scope><orcidid>https://orcid.org/0000-0003-3386-7658</orcidid></search><sort><creationdate>20201101</creationdate><title>Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities</title><author>Echabbi, L. ; Fourneau, J.M. ; Gacem, O. ; Lotfi, H. ; Pekergin, N.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c332t-71e116a84beae4f7d78d253817b74a96bc34fc5232c835f0014cfe23330fad813</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Computer Science</topic><topic>Increasing convex ordering</topic><topic>Maximal flow</topic><topic>Modeling and Simulation</topic><topic>Random capacity</topic><topic>Stochastic ordering</topic><toplevel>online_resources</toplevel><creatorcontrib>Echabbi, L.</creatorcontrib><creatorcontrib>Fourneau, J.M.</creatorcontrib><creatorcontrib>Gacem, O.</creatorcontrib><creatorcontrib>Lotfi, H.</creatorcontrib><creatorcontrib>Pekergin, N.</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Electronic notes in theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Echabbi, L.</au><au>Fourneau, J.M.</au><au>Gacem, O.</au><au>Lotfi, H.</au><au>Pekergin, N.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities</atitle><jtitle>Electronic notes in theoretical computer science</jtitle><date>2020-11-01</date><risdate>2020</risdate><volume>353</volume><spage>77</spage><epage>105</epage><pages>77-105</pages><issn>1571-0661</issn><eissn>1571-0661</eissn><abstract>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.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.entcs.2020.10.014</doi><tpages>29</tpages><orcidid>https://orcid.org/0000-0003-3386-7658</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1571-0661
ispartof Electronic notes in theoretical computer science, 2020-11, Vol.353, p.77-105
issn 1571-0661
1571-0661
language eng
recordid cdi_hal_primary_oai_HAL_hal_04345108v1
source BACON - Elsevier - GLOBAL_SCIENCEDIRECT-OPENACCESS
subjects Computer Science
Increasing convex ordering
Maximal flow
Modeling and Simulation
Random capacity
Stochastic ordering
title Stochastic Bounds for the Max Flow in a Network with Discrete Random Capacities
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T17%3A08%3A22IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-hal_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Stochastic%20Bounds%20for%20the%20Max%20Flow%20in%20a%20Network%20with%20Discrete%20Random%20Capacities&rft.jtitle=Electronic%20notes%20in%20theoretical%20computer%20science&rft.au=Echabbi,%20L.&rft.date=2020-11-01&rft.volume=353&rft.spage=77&rft.epage=105&rft.pages=77-105&rft.issn=1571-0661&rft.eissn=1571-0661&rft_id=info:doi/10.1016/j.entcs.2020.10.014&rft_dat=%3Chal_cross%3Eoai_HAL_hal_04345108v1%3C/hal_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c332t-71e116a84beae4f7d78d253817b74a96bc34fc5232c835f0014cfe23330fad813%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true