Computer Science – Discrete Mathematics
Scientific paper
2009-03-01
CPAIOR 2009
Computer Science
Discrete Mathematics
Accepted at the Sixth International Conference on integration of AI and OR Techniques in Constraint Programming for Combinator
Scientific paper
The interdiction problem arises in a variety of areas including military logistics, infectious disease control, and counter-terrorism. In the typical formulation of network interdiction, the task of the interdictor is to find a set of edges in a weighted network such that the removal of those edges would maximally increase the cost to an evader of traveling on a path through the network. Our work is motivated by cases in which the evader has incomplete information about the network or lacks planning time or computational power, e.g. when authorities set up roadblocks to catch bank robbers, the criminals do not know all the roadblock locations or the best path to use for their escape. We introduce a model of network interdiction in which the motion of one or more evaders is described by Markov processes and the evaders are assumed not to react to interdiction decisions. The interdiction objective is to find an edge set of size B, that maximizes the probability of capturing the evaders. We prove that similar to the standard least-cost formulation for deterministic motion this interdiction problem is also NP-hard. But unlike that problem our interdiction problem is submodular and the optimal solution can be approximated within 1-1/e using a greedy algorithm. Additionally, we exploit submodularity through a priority evaluation strategy that eliminates the linear complexity scaling in the number of network edges and speeds up the solution by orders of magnitude. Taken together the results bring closer the goal of finding realistic solutions to the interdiction problem on global-scale networks.
Gutfraind Alexander
Hagberg Aric
Pan Feng
No associations
LandOfFree
Optimal Interdiction of Unreactive Markovian Evaders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Interdiction of Unreactive Markovian Evaders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Interdiction of Unreactive Markovian Evaders will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-77349