Center Selection Problem: Center for a Single Site

  • Thread starter zak100
  • Start date
  • #1
zak100
Gold Member
462
11

Summary:

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

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
1,955
252
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.
 

Related Threads on Center Selection Problem: Center for a Single Site

  • Last Post
Replies
4
Views
327
Replies
1
Views
2K
  • Last Post
Replies
5
Views
666
Replies
5
Views
420
  • Last Post
Replies
2
Views
11K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
667
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
2K
Top