What type of algorithm would be appropriate here?

Question

I need to develop an algorithm to solve the following problem:

Consider the line L in the plane. The final set T of targets is located above the line L, and the final set S of wireless sensors is located below the line L. The sensor s can control the target t if and only if the Euclidean distance between s and t is not more than one. Suppose each s & in; S has a positive value c (s) and each target t & in; T can be controlled by at least one sensor in S. Consider that a subset S0 of sensors in S. S0 is considered a cover if each target in T is covered by at least one sensor in S0. The cost of S0 is the total cost of the sensors in S0. The goal is to calculate the minimum cost coverage S0. Please develop a polynomial time algorithm and write a program for its implementation.

I really don't know what type of algorithm I could use for this (greedy, dynamic, divide and conquer). I am not looking for an answer, not a hint on how to proceed. How do I approach this problem?

Answer 1

Take a look here http://www.pressingquestion.com/3830657/Computing-Minimum-Cost-With-Using-Dynamic-Programming . This is a question very similar to yours. The solution to this question indicates that your question is NP-Hard, not polynomial. However, if you slightly modify your question so that these goals are on the line, and not higher , then you can use the dynamic programming approach to solve it. Details are indicated in the link.

, , , . " ". (, L x, x), . , , ( 1) , . , , .