Distributionally Robust Max Flows
Loading...
Authors
Chen, Louis L.
Ma, Will
Orlin, James B.
Simchi-Levi, David
Subjects
Advisors
Date of Issue
2020
Date
Publisher
Society for Industrial and Applied Mathematics (SIAM)
Language
Abstract
We study a distributionally robust max flow problem under the marginal distribution model, where the vector of arc capacities is random, with the marginals to the joint multivariate distribution being known, but the correlation being unknown. The goal is to compute the expected value of the max flow under the worst-case joint distribution of arc capacities. We provide a simple combinatorial proof that shows that for the case of finite-supported marginal distributions, this worst-case expectation can be efficiently computed, and moreover, the worst-case joint distribution can be explicitly constructed, despite being non-trivial in the sense that it is not a combination of monotonic or anti-monotonic couplings. Our technique is to use a related min-cost flow problem to generate a distribution over cuts in the graph, which in turn induces the worst-case joint distribution. It also provides an alternative interpretation of the problem as a zero-sum game between a capacity player and a cut player.
Type
Conference Paper
Description
Symposium on Simplicity in Algorithms. Society for Industrial and Applied Mathematics, 2020.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
10 p.
Citation
Chen, Louis L., et al. "Distributionally Robust Max Flows." Symposium on Simplicity in Algorithms. Society for Industrial and Applied Mathematics, 2020.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.