Evader interdiction: algorithms, complexity and collateral damage
From MaRDI portal
Publication:490228
Abstract: In network interdiction problems, evaders (e.g., hostile agents or data packets) may be moving through a network towards targets and we wish to choose locations for sensors in order to intercept the evaders before they reach their destinations. The evaders might follow deterministic routes or Markov chains, or they may be reactive}, i.e., able to change their routes in order to avoid sensors placed to detect them. The challenge in such problems is to choose sensor locations economically, balancing security gains with costs, including the inconvenience sensors inflict upon innocent travelers. We study the objectives of 1) maximizing the number of evaders captured when limited by a budget on sensing cost and 2) capturing all evaders as cheaply as possible. We give optimal sensor placement algorithms for several classes of special graphs and hardness and approximation results for general graphs, including for deterministic or Markov chain-based and reactive or oblivious evaders. In a similar-sounding but fundamentally different problem setting posed by Rubinstein and Glazer where both evaders and innocent travelers are reactive, we again give optimal algorithms for special cases and hardness and approximation results on general graphs.
Recommendations
- On the interrelationship of two problems on evasion with many evaders
- Network interdiction to minimize the maximum probability of evasion with synergy between applied resources
- Evasion from detection by a system of heterogeneous observers in threat environment
- Evasion in a certain class of distributed control systems
- Optimal evading strategies and task allocation in multi-player pursuit-evasion problems
- On the ``equivalence of two evasion problems with multiple evaders
- Pursuit and evasion from a distance: algorithms and bounds
- Optimal Interdiction of Unreactive Markovian Evaders
- On the interrelation of two linear stationary evasion problems with many evaders
Cites work
- scientific article; zbMATH DE number 1256776 (Why is no real title available?)
- scientific article; zbMATH DE number 2050720 (Why is no real title available?)
- A threshold of ln n for approximating set cover
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Approximating the k-multicut problem
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Fast stabbing of boxes in high dimensions
- Finding All the Elementary Circuits of a Directed Graph
- Finding the n Most Vital Links in Flow Networks
- Finding the n Most Vital Nodes in a Flow Network
- Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Improved approximation for directed cut problems
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Maintenance of a piercing set for intervals with applications
- Most vital links and nodes in weighted networks
- On the positive-negative partial set cover problem
- Optimal Interdiction of Unreactive Markovian Evaders
- Optimal interdiction of a supply network
- Partial multicuts in trees
- Polynomial flow-cut gaps and hardness of directed cut problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Some simplified NP-complete graph problems
- Submodular Function Minimization under Covering Constraints
- The Maximum Coverage Location Problem
- The checkpoint problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(9)- Optimal Interdiction of Unreactive Markovian Evaders
- Network interdiction to minimize the maximum probability of evasion with synergy between applied resources
- A two‐stage network interdiction‐monitoring game
- Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption
- Pessimistic evasive flow capturing problems
- A decomposition approach for stochastic shortest-path network interdiction with goal threshold
- Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback
- Adaptivity in network interdiction
- Infrastructure security games
This page was built for publication: Evader interdiction: algorithms, complexity and collateral damage
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490228)
