On the power of randomization in network interdiction

In this paper, 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.

• Publication year

  2013

• Venue

  Operations Research Letters

• Publication date

  2013-12-12

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.orl.2015.11.005arXiv 1312.3478
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Robust and Adaptive Network Flows

  2013cited by this paper
• Finding the N most vital links in flow networks

  2011cited by this paper
• Network Flows

  2011cited by this paper
• A bi-objective approach for shortest-path network interdiction

  2010cited by this paper
• Shortest path network interdiction with asymmetric information

  2008cited by this paper
• Reformulation and sampling to solve a stochastic network interdiction problem

  2008cited by this paper
• The vehicle rescheduling problem: Model and algorithms

  2007cited by this paper
• Critical network infrastructure analysis: interdiction and system flow

  2007cited by this paper
• The maximum residual flow problem: NP‐hardness with two‐arc destruction

  2007cited by this paper
• Algorithms for discrete and continuous multicommodity flow network interdiction problems

  2007cited by this paper
• Solving the Bi-Objective Maximum-Flow Network-Interdiction Problem

  2007cited by this paper
• Analysis of electric grid security under terrorist threat

  2004cited by this paper
• A Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition

  2003influential reference
• Shortest‐path network interdiction

  2002cited by this paper
• Maximizing residual flow under an arc destruction

  2001cited by this paper
• Improving Single Strike Effectiveness for Network Interdiction

  1999cited by this paper
• Stochastic Network Interdiction

  1998cited by this paper
• The network inhibition problem

  1993cited by this paper
• Deterministic network interdiction

  1993cited by this paper
• Network Flows: Theory, Algorithms, and Applications

  1993influential reference
• Network Interdiction Models

  1991cited by this paper
• A network interdiction model for hospital infection control.

  1987cited by this paper
• Finding the n Most Vital Nodes in a Flow Network

  1974cited by this paper
• Removing Arcs from a Network

  1964cited by this paper
• Statistical Decision Functions Which Minimize the Maximum Risk

  1945cited by this paper
• FINDING THE n MOST VITAL LINKS IN FLOW NETWORKS

  year unknowncited by this paper

• Interdiction in network maximum flow and related problems: A survey

  2026cites this paper
• Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction

  2025cites this paper
• Randomized Assortment Optimization

  2024cites this paper
• Contested Logistics: A Game-Theoretic Approach

  2024cites this paper
• Inspection Game with Location-Specific Detection Capabilities

  2024cites this paper
• The all-pairs vitality-maximization (VIMAX) problem

  2023influential citation
• Network Inspection Using Heterogeneous Sensors for Detecting Strategic Attacks

  2023cites this paper
• Randomized Robust Price Optimization

  2023cites this paper
• Hide-and-Seek Game with Capacitated Locations and Imperfect Detection

  2023cites this paper
• A two‐stage network interdiction‐monitoring game

  2022cites this paper
• The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems

  2022cites this paper
• Decomposition of probability marginals for security games in max-flow/min-cut systems

  2022cites this paper
• Attacking Shortest Paths by Cutting Edges

  2022cites this paper
• Decomposition of Probability Marginals for Security Games in Abstract Networks

  2022cites this paper
• Network Inspection from Locations with Imperfect Detection Capabilities

  2022cites this paper
• Robust static and dynamic maximum flows

  2022cites this paper
• Joint optimizing network interdiction and emergency facility location in terrorist attacks

  2020cites this paper
• Robust Maximum Flow Network Interdiction Problem

  2020cites this paper
• The value of randomized strategies in distributionally robust risk averse network interdiction games

  2020influential citation
• Security metrics and allocation of security resources for control systems

  2020cites this paper
• Dynamic interdiction networks with applications in illicit supply chains

  2020cites this paper
• Project management in a competitive environment: interdicting a CPM based project and its implications

  2019cites this paper
• A two-stage model for period-dependent traffic signal control in a road networked system with stochastic travel demand

  2019cites this paper
• Network Interdiction Using Adversarial Traffic Flows

  2019cites this paper
• A Network Monitoring Game with Heterogeneous Component Criticality Levels

  2019cites this paper
• A Decomposition Approach for Stochastic Shortest-Path Network Interdiction with Goal Threshold

  2019cites this paper
• Bi-objective optimization models for network interdiction

  2019cites this paper
• A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games

  2019cites this paper
• An Iterative Security Game for Computing Robust and Adaptive Network Flows

  2019cites this paper
• Algorithms and complexity results for packing and covering problems and robust dynamic network flows under primal-dual aspects

  2018cites this paper
• Shortest Path Network Interdiction With Goal Threshold

  2018cites this paper
• A robust signal control system for equilibrium flow under uncertain travel demand and traffic delay

  2018cites this paper
• Probability Distributions on Partially Ordered Sets and Network Security Games

  2018cites this paper
• Probability Distributions on Partially Ordered Sets and Network Interdiction Games

  2018cites this paper
• Network Inspection for Detecting Strategic Attacks

  2017cites this paper
• Computational Methods for Path-based Robust Flows

  2017influential citation
• Rerouting Flows When Links Fail

  2017cites this paper
• The Complexity of Computing a Robust Flow

  2017cites this paper
• Two extended formulations for cardinality maximum flow network interdiction problem

  2017cites this paper
• Network Monitoring under Strategic Disruptions

  2017cites this paper
• Protection of flows under targeted attacks

  2016cites this paper
• "Dice"-sion-Making Under Uncertainty: When Can a Random Decision Reduce Risk?

  2016cites this paper
• Network security and min-cost max-flow problem

  2016cites this paper
• Security games on infrastructure networks

  2016cites this paper
• Parametric multiroute flow and its application to multilink-attack network

  2016cites this paper
• Optimization of information flows in telecommunication networks

  2016cites this paper
• Robust randomized matchings

  2015influential citation
• Analysis of approximation and uncertainty in optimization

  2015cites this paper
• Network flow routing under strategic link disruptions

  2015cites this paper
• Security Games in Network Flow Problems

  2015cites this paper
• Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty

  2014cites this paper
• A sequential algorithm for the bilevel network interdiction problem

  year unknowncites this paper