On the power of randomization in network interdiction

DOI10.1016/J.ORL.2015.11.005zbMATH Open1408.91038arXiv1312.3478OpenAlexW1738845896MaRDI QIDQ1785482FDOQ1785482

Authors: Ebrahim Nasrabadi, James B. Orlin, Dimitris Bertsimas 

Publication date: 28 September 2018

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

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}$.

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

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

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)

Cites Work

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

Cited In (16)

• Decomposition of probability marginals for security games in abstract networks
• Protection of flows under targeted attacks
• A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
• Network Inspection for Detecting Strategic Attacks
• Rerouting Flows when Links Fail
• The all-pairs vitality-maximization (VIMAX) problem
• Parametric multiroute flow and its application to multilink-attack network
• A robust signal control system for equilibrium flow under uncertain travel demand and traffic delay
• Robust Randomized Matchings
• Title not available (Why is that?)
• Bi-objective optimization models for network interdiction
• The complexity of computing a robust flow
• An iterative security game for computing robust and adaptive network flows
• A two‐stage network interdiction‐monitoring game
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games
• A decomposition approach for stochastic shortest-path network interdiction with goal threshold

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)