Name
Abstract | ||
|---|---|---|
The Unreactive Markovian Evader Interdiction Problem (UME) asks to optimally
place sensors on a network to detect Markovian motion by one or more "evaders".
It was previously proved that finding the optimal sensor placement is NP-hard
if the number of evaders is unbounded. Here we show that the problem is NP-hard
with just 2 evaders using a connection to coloring of planar graphs. The
results suggest that approximation algorithms are needed even in applications
where the number of evaders is small. It remains an open problem to determine
the complexity of the 1-evader case or to devise efficient algorithms. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | planar graph,discrete mathematics,computational complexity |
Field | DocType | Volume |
Approximation algorithm,Discrete mathematics,Combinatorics,Open problem,Markov process,Four color theorem,Interdiction,Mathematics,Planar graph | Journal | abs/0911.4 |
Citations | PageRank | References |
1 | 0.36 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Gutfraind | 1 | 28 | 7.37 |
| Kiyan Ahmadizadeh | 2 | 42 | 4.27 |