Evader interdiction: algorithms, complexity and collateral damage
From MaRDI portal
Publication:490228
DOI10.1007/S10479-013-1372-XzbMATH Open1303.90058arXiv1108.0894OpenAlexW1973266786WikidataQ34361359 ScholiaQ34361359MaRDI QIDQ490228FDOQ490228
Authors: Matthew P. Johnson, Alexander Gutfraind, Kiyan Ahmadizadeh 
Publication date: 22 January 2015
Published in: Annals of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1108.0894
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
- A threshold of ln n for approximating set cover
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Some simplified NP-complete graph problems
- The Maximum Coverage Location Problem
- Submodular Function Minimization under Covering Constraints
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Finding the n Most Vital Links in Flow Networks
- Most vital links and nodes in weighted networks
- Optimal Interdiction of Unreactive Markovian Evaders
- Title not available (Why is that?)
- Finding the n Most Vital Nodes in a Flow Network
- Optimal interdiction of a supply network
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Fast stabbing of boxes in high dimensions
- Title not available (Why is that?)
- Approximating the k-multicut problem
- Polynomial flow-cut gaps and hardness of directed cut problems
- Improved approximation for directed cut problems
- Maintenance of a piercing set for intervals with applications
- Finding All the Elementary Circuits of a Directed Graph
- 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
- The checkpoint problem
- Partial multicuts in trees
- On the positive-negative partial set cover problem
Cited In (8)
- Network interdiction to minimize the maximum probability of evasion with synergy between applied resources
- Optimal Interdiction of Unreactive Markovian Evaders
- Pessimistic evasive flow capturing problems
- Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback
- Infrastructure security games
- Adaptivity in network interdiction
- Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption
- A decomposition approach for stochastic shortest-path network interdiction with goal threshold
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)
