The complexity of computing a robust flow

DOI10.1016/J.ORL.2019.10.012MaRDI QIDQ2294522zbMATH OpenOpenAlexFDO

Authors Y. Disser, Jannik Matuschke

Publication date 11 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.08241

zbMATH Keywords

network flowscomplexity theoryrobust optimizationnetwork interdiction

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• On robust maximum flow with polyhedral uncertainty sets
• A (k + 1)-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow
• Hardness of robust network design
• Robust and adaptive network flows
• Robust minimum cost flow problem under consistent flow constraints

Cites work

• Deterministic network interdiction
• Geometric algorithms and combinatorial optimization
• Hardness and approximation for network flow interdiction
• Maximizing residual flow under an arc destruction
• Network flows. Theory, algorithms, and applications.
• On multiroute maximum flows in networks.
• On the power of randomization in network interdiction
• Parametric multiroute flow and its application to multilink-attack network
• Protection of flows under targeted attacks
• Rerouting flows when links fail
• Robust and adaptive network flows
• Robust discrete optimization and network flows
• Robust flows over time: models and complexity results
• The directed subgraph homeomorphism problem
• The maximum residual flow problem: NP‐hardness with two‐arc destruction

Cited in

(11)

• Constrained flows in networks
• Rerouting Flows when Links Fail
• The complexity of flow on fat terrains and its i/o-efficient computation
• scientific article; zbMATH DE number 1148567 (Why is no real title available?)
• A \((B + 1)\)-approximation for network flow interdiction with unit costs
• Algorithmic results for potential‐based flows: Easy and hard cases
• Robust flows with adaptive mitigation
• Complexity of a classical flow restoration problem
• Decomposition of probability marginals for security games in abstract networks
• Robust transshipment problem under consistent flow constraints
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games

This page was built for publication: The complexity of computing a robust flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294522)