Center Selection Problem: Center for a single site

[zak100]

Hi,

Quote

 

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.

 

Zulfi.

[fiveworlds]

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.