Evader interdiction: algorithms, complexity and collateral damage

Matthew Johnson, Alexander Gutfraind () and Kiyan Ahmadizadeh

Annals of Operations Research, 2014, vol. 222, issue 1, 359 pages

Abstract: In network interdiction problems, evaders (e.g., hostile agents or data packets) are moving through a network toward targets and we wish to choose locations for sensors in order to intercept the evaders. 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 the sensors. The challenge in such problems is to choose sensor locations economically, balancing interdiction 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 algorithms for optimal sensor placement in several classes of special graphs and hardness and approximation results for general graphs, including evaders who are deterministic, Markov chain-based, reactive and unreactive. A similar-sounding but fundamentally different problem setting was posed by Glazer and Rubinstein where both evaders and innocent travelers are reactive. We again give optimal algorithms for special cases and hardness and approximation results on general graphs. Copyright Springer Science+Business Media New York 2014

Keywords: Network interdiction; Bridge policy; Submodular set cover; Markov chain; Minimal cut; Four color theorem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-013-1372-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:222:y:2014:i:1:p:341-359:10.1007/s10479-013-1372-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-013-1372-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().