On the power of randomization in network interdiction

DOI10.1016/J.ORL.2015.11.005MaRDI QIDQ1785482zbMATHOpenAlexFDO

Authors Ebrahim Nasrabadi, James B. Orlin, Dimitris Bertsimas

Publication date 28 September 2018

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

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

zbMATH Keywords

game theorynetwork flowsapproximationinterdiction

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Games involving graphs (91A43)

Abstract: Network interdiction can be viewed as a game between two players, an "interdictor" and a "flow player". The flow player wishes to send as much material as possible through a network, while the interdictor attempts to minimize the amount of transported material by removing a certain number of arcs, say $Gamma$ arcs. We introduce the randomized network interdiction problem that allows the interdictor to use randomness to select arcs to be removed. We model the problem in two different ways: arc-based and path-based formulations, depending on whether flows are defined on arcs or paths, respectively. We present insights into the modeling power, complexity, and approximability of both formulations. In particular, we prove that $Z_{extNI}/Z_{extRNI}leqGamma+1$, $Z_{extNI}/Z_{extRNI}^{extPath}leqGamma+1$, $Z_{extRNI}/Z_{extRNI}^{extPath}leqGamma$, where $Z_{extNI}$, $Z_{extRNI}$, and $Z_{extRNI}^{extPath}$ are the optimal values of the network interdiction problem and its randomized versions in arc-based and path-based formulations, respectively. We also show that these bounds are tight. We show that it is NP-hard to compute the values $Z_{extRNI}$ and $Z_{extRNI}^{extPath}$ for a general $Gamma$, but they are computable in polynomial time when $Gamma=1$. Further, we provide a $(Gamma+1)$-approximation for $Z_{extNI}$, a $Gamma$-approximation for $Z_{extRNI}$, and a $$-approximation for $Z_{extRNI}^{extPath}$.

Recommendations

• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms
• scientific article; zbMATH DE number 2050723
• Reformulation and sampling to solve a stochastic network interdiction problem
• Deterministic network interdiction
• Network interdiction with asymmetric cost uncertainty

Cites work

• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• Deterministic network interdiction
• Finding the n Most Vital Links in Flow Networks
• Maximizing residual flow under an arc destruction
• Network flows. Theory, algorithms, and applications.
• Reformulation and sampling to solve a stochastic network interdiction problem
• Removing Arcs from a Network
• Robust and adaptive network flows
• Shortest path network interdiction with asymmetric information
• Shortest-path network interdiction
• Solving the bi-objective maximum-flow network-interdiction problem
• Stochastic network interdiction
• The maximum residual flow problem: NP‐hardness with two‐arc destruction
• The network inhibition problem

Cited in

(19)

• The all-pairs vitality-maximization (VIMAX) problem
• An iterative security game for computing robust and adaptive network flows
• Rerouting Flows when Links Fail
• A two‐stage network interdiction‐monitoring game
• Robust randomized matchings
• The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems
• Protection of flows under targeted attacks
• Decomposition of probability marginals for security games in abstract networks
• Network inspection for detecting strategic attacks
• Bi-objective optimization models for network interdiction
• A survey of network interdiction models and algorithms
• A decomposition approach for stochastic shortest-path network interdiction with goal threshold
• A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
• A linear input dependence model for interdependent networks
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• scientific article; zbMATH DE number 2050723 (Why is no real title available?)
• A robust signal control system for equilibrium flow under uncertain travel demand and traffic delay
• Parametric multiroute flow and its application to multilink-attack network
• The complexity of computing a robust flow

This page was built for publication: On the power of randomization in network interdiction

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