Distributionally Robust Max Flows with Marginals

In this paper, we extend the study of Chen et al 2018 to the problem of distributionally robust network design. In this problem, the decision maker is to decide on the prepositioning of resources on arcs in a given s-t flow network in anticipation of an adversary’s selection of a probability distribution for the arc capacities that seeks to minimize the expected max flow. The adversary’s selection is limited to those distributions that are couplings of given arc capacity distributions, one for each arc. We find that modeling the uncertainty in this way is certainly more sensible than prescribing the stochastic behavior of the arc capacities across an entire network. Furthermore, while it is hard to compute even the expectation with respect to the independent coupling of the stochastic arc capacities, we show that we can efficiently solve the distributionally robust network design problem. Indeed, this particular problem satisfies the sufficiency condition for tractability that we proposed in the previous work. But what’s more, a highlight and extension in this work is to take advantage of the network setting to go even further and efficiently solve for the distribution the adversary responds with. Download paper here

Recommended citation: Your Name, You. (2020). “Distributionally Robust Max Flows with Marginals.” SOSA 2020 1. 1(2).