[Solved]: Minimum cost subset of sensors covering targets

Problem Detail: 

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.

Asked By : farajnew

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6839

3.2K people like this

 Download Related Notes/Documents