Center Selection Problem: Center for a Single Site

[zak100]

TL;DR

Hi,
I am trying to understand a book material related to greedy approach for determining a center for a single site

Algorithm 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 word single center, is this single center or single site? What is coverng radius? Why it can have bad solution?

Somebody please guide me.

Zulfi.

 

[willem2]

Summary:: Hi,
I am trying to understand a book material related to greedy approach for determining a center for a single site

I have underlined the word single center, is this single center or single site? What is coverng radius? Why it can have bad solution?

The greedy algorithm places the centers one by one. When it places the first center it solves the problem with the same sites but only one center. When it places the second center the first center will remain fixed and only the position of the second center is considered.

The covering radius is the mimimum radius of the circles you need to draw around all centers cover all sites.

An obvious bad solution: You are allowed 2 centers, and sites in Los Angeles, San Francisco, New York, and Washinton. The greedy Algorithm would place the first center somewhere in Kansas. No matter where you place the second center, either the east coast cities or the west coast cities need to be served from Kansas, making the minimum covering radius about 1500 miles instead of 200 miles.