Premium
Security routing games with multivehicle C hinese postman problem
Author(s) -
Hochbaum Dorit S.,
Lyu Cheng,
Ordóñez Fernando
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21563
Subject(s) - stackelberg competition , patrolling , computer science , computer security , adversary , key (lock) , decomposition , software deployment , operations research , mathematics , mathematical economics , ecology , political science , law , biology , operating system
Key in the efforts to deter and prevent nuclear terrorism is the ability to detect the presence of possible nuclear threats in a given area. Resources capable of detecting such threats are limited, expensive, and only capable of scanning a certain total area in a given amount of time. This limit on the ability to detect nuclear threats makes imperative the development of efficient deployment strategies of the detection resources. In this work, we propose a Stackelberg game‐based model to determine the optimal patrolling strategy of security assets over a network in the presence of a strategic adversary that seeks to place a nuclear threat on edges of the network. To efficiently solve this model, we introduce a novel decomposition of the problem which requires the solution of a multivehicle rural Chinese postman problem (CPP). Our theoretical contributions present hardness and approximation results for the k‐vehicle rural CPP. Our computational results demonstrate the benefit of this decomposition for the nuclear threat detection security problem. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 181–191 2014