Jump to content

Center Selection Problem: Center for a single site


Recommended Posts




I am trying to understand center selection problem in the context of greedy approach.   We now discuss greedy algorithms for this problem. As before, the meaning of “greedy” here is necessarily  a little fuzzy; essentially, we consider algorithms that select sites one by one in  a myopic fashion—that is, choosing each without explicitly considering where  the remaining sites will go. 

Probably the simplest greedy algorithm would work as follows. It would  put the first center at the best possible location for a single center, then keep  adding centers so as to reduce the covering radius, each time, by as much as  possible. It turns out that this approach is a bit too simplistic to be effective:  there are cases where it can lead to very bad solutions.


I have underlined the words "single center",  will this be single site. I can't understand this greedy approach? why its bad?


Somebody please guide me.



Link to comment
Share on other sites

  • 2 weeks later...

The greedy approach is bad because it doesn't find the optimum solution. Once a site has been selected it cannot be changed. It can lead to situations where one site is responsible for a large area in comparison to other selected sites.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.