# Minimizing cost with selection

I have the following problem:

Suppose that we have several points that cover some cities, with a cost associated to each point. This can be represented as a grid:

  c1  c2  c3  c4  c5 cost
p1 1  0   1   0   1  200
p2 1  1   1   0   0  100
p3 0  1   0   1   1  300
...


etc. Where $$c_n$$ represents a city, and $$p_m$$ a point that connects the cities marked with $$1$$. Each point has a cost associated. My question is how to select those points in a way that they cover all the cities with minimum cost. If there is not a selection of points, the algorithm should inform about it.

• I probably didn't really understand your question, but what is keeping you from choosing the "point" with the lowest cost for each city? Oct 7, 2021 at 22:58
• @nirshahar that maybe there is a point that covers more than one city at a bigger cost, but it's the optimal in the long-term Oct 7, 2021 at 22:59
• This problem is NP hard even if all $p_i$'s are the same. Check Set cover problem. Oct 8, 2021 at 1:45