Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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