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.

  • $\begingroup$ I probably didn't really understand your question, but what is keeping you from choosing the "point" with the lowest cost for each city? $\endgroup$
    – nir shahar
    Oct 7 at 22:58
  • $\begingroup$ @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 $\endgroup$
    – Norhther
    Oct 7 at 22:59
  • $\begingroup$ This problem is NP hard even if all $p_i$'s are the same. Check Set cover problem. $\endgroup$
    – John L.
    Oct 8 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.