I have a dynamic programming problem:

If I have a set of sensors covering targets (a target might be covered by mutiple sensors) how can I find the minimum cost subset of sensors covering all targets given each sensor has a cost?

I have thought a lot about this, but I can't reach the recursive formula to write my program. The greedy algorithm does not always provide the correct minimum cost subset. My problem is that sensors overlap in covering targets. Any help?

Example: I have set of sensors $\{s_1,s_2,s_3\}$ with costs $\{1,\frac{5}{2},2\}$ and 3 targets $\{t_1,t_2,t_3\}$. Sensors cover $\{t_1 t_2,t_1 t_2 t_3,t_2 t_3\}$ and I need to get minimum cost subset by dynamic programming. For the above example if I use greedy algorithm I would get $s_1,s_3$ but the right answer is $s_2$ only.


1 Answer 1


Your problem is equivalent to the weighted version of Set Cover, which is NP-complete (and delving into other complexity classifications, W[2]-complete and inapproximable within $O(\log n)$).

If you want a polynomial-time algorithm, you're going to have to impose restrictions on either your problem or the input.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.