0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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, 2021 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, 2021 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, 2021 at 1:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.