Computer Science – Social and Information Networks
Scientific paper
2011-08-03
Computer Science
Social and Information Networks
Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobil
Scientific paper
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.
Gutfraind Alexander
Johnson Matthew P.
No associations
LandOfFree
Evader Interdiction and Collateral Damage 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 Evader Interdiction and Collateral Damage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evader Interdiction and Collateral Damage will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664513