IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v222y2014i1p341-35910.1007-s10479-013-1372-x.html
   My bibliography  Save this article

Evader interdiction: algorithms, complexity and collateral damage

Author

Listed:
  • Matthew Johnson
  • Alexander Gutfraind
  • Kiyan Ahmadizadeh

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

Suggested Citation

  • Matthew Johnson & Alexander Gutfraind & Kiyan Ahmadizadeh, 2014. "Evader interdiction: algorithms, complexity and collateral damage," Annals of Operations Research, Springer, vol. 222(1), pages 341-359, November.
    • Handle: RePEc:spr:annopr:v:222:y:2014:i:1:p:341-359:10.1007/s10479-013-1372-x
    DOI: 10.1007/s10479-013-1372-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-013-1372-x
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-013-1372-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. H. Donald Ratliff & G. Thomas Sicilia & S. H. Lubore, 1975. "Finding the n Most Vital Links in Flow Networks," Management Science, INFORMS, vol. 21(5), pages 531-539, January.
    2. Alan W. McMasters & Thomas M. Mustin, 1970. "Optimal interdiction of a supply network," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 17(3), pages 261-268, September.
    3. H. W. Corley, Jr. & Han Chang, 1974. "Finding the n Most Vital Nodes in a Flow Network," Management Science, INFORMS, vol. 21(3), pages 362-364, November.
    4. , & ,, 2006. "A study in the pragmatics of persuasion: a game theoretical approach," Theoretical Economics, Econometric Society, vol. 1(4), pages 395-410, December.
    5. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Jing & Zhuang, Jun & Behlendorf, Brandon, 2018. "Stochastic shortest path network interdiction with a case study of Arizona–Mexico border," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 62-73.
    2. Jing Yang & Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2021. "Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback," Decision Analysis, INFORMS, vol. 18(3), pages 218-244, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tony H. Grubesic & Timothy C. Matisziw & Alan T. Murray & Diane Snediker, 2008. "Comparative Approaches for Assessing Network Vulnerability," International Regional Science Review, , vol. 31(1), pages 88-112, January.
    2. Alice Paul & Susan E. Martonosi, 2024. "The all-pairs vitality-maximization (VIMAX) problem," Annals of Operations Research, Springer, vol. 338(2), pages 1019-1048, July.
    3. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    4. Alan Murray & Timothy Matisziw & Tony Grubesic, 2007. "Critical network infrastructure analysis: interdiction and system flow," Journal of Geographical Systems, Springer, vol. 9(2), pages 103-117, June.
    5. Jabarzare, Ziba & Zolfagharinia, Hossein & Najafi, Mehdi, 2020. "Dynamic interdiction networks with applications in illicit supply chains," Omega, Elsevier, vol. 96(C).
    6. Kosanoglu, Fuat & Bier, Vicki M., 2020. "Target-oriented utility for interdiction of transportation networks," Reliability Engineering and System Safety, Elsevier, vol. 197(C).
    7. Gabriele Dragotto & Amine Boukhtouta & Andrea Lodi & Mehdi Taobane, 2024. "The critical node game," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-20, July.
    8. Winand Emons & Claude Fluet, 2019. "Strategic communication with reporting costs," Theory and Decision, Springer, vol. 87(3), pages 341-363, October.
    9. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.
    10. Elliot Lipnowski & Doron Ravid, 2020. "Cheap Talk With Transparent Motives," Econometrica, Econometric Society, vol. 88(4), pages 1631-1660, July.
    11. Matthias Lang, 2020. "Mechanism Design with Narratives," CESifo Working Paper Series 8502, CESifo.
    12. Rodríguez-Núñez, Eduardo & García-Palomares, Juan Carlos, 2014. "Measuring the vulnerability of public transport networks," Journal of Transport Geography, Elsevier, vol. 35(C), pages 50-63.
    13. P. Milgrom, 2009. "What the Seller Wont Tell You: Persuasion and Disclosure in Markets," Voprosy Ekonomiki, NP Voprosy Ekonomiki, issue 3.
    14. Jacob Glazer & Ariel Rubinstein, 2012. "A Model of Persuasion with Boundedly Rational Agents," Journal of Political Economy, University of Chicago Press, vol. 120(6), pages 1057-1082.
    15. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    16. Alessandro Ispano & Péter Vida, 2020. "Custodial Interrogations," THEMA Working Papers 2020-05, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    17. Bloch, Francis & Chatterjee, Kalyan & Dutta, Bhaskar, 2023. "Attack and interception in networks," Theoretical Economics, Econometric Society, vol. 18(4), November.
    18. Hugo M. Mialon & Sue H. Mialon, 2013. "Go Figure: The Strategy of Nonliteral Speech," American Economic Journal: Microeconomics, American Economic Association, vol. 5(2), pages 186-212, May.
    19. Burdea, Valeria & Montero, Maria & Sefton, Martin, 2023. "Communication with partially verifiable information: An experiment," Games and Economic Behavior, Elsevier, vol. 142(C), pages 113-149.
    20. Tolga H. Seyhan & Lawrence V. Snyder & Ying Zhang, 2018. "A New Heuristic Formulation for a Competitive Maximal Covering Location Problem," Transportation Science, INFORMS, vol. 52(5), pages 1156-1173, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:222:y:2014:i:1:p:341-359:10.1007/s10479-013-1372-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.