0

I am trying to understand the following text which defines a greedy algorithm for center selection problem:

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.

Kleinberg, Jon. Algorithm Design (p. 607). Pearson Education. Kindle Edition.

Is the term "single center" typo for "single site"?

Useful link is: Euclidean K-Center Problem

Somebody please guide me how by adding centers we can reduce the covering radius? Why it has bad solutions.

Zulfi.

RobPratt
  • 45,619
zak100
  • 177

1 Answers1

1

Suppose we have $9$ demand points, arranged in $3$ groups. The points in each group are located at the vertices of a small equilateral triangle, and the centers of these triangles are located at the vertices of a large equilateral triangle. We are to place $3$ supply points. Obviously, the optimum is to place one at the center of each small triangle, but the greedy algorithm will place the first at the center of the large triangle. Whatever happens next, we'll have a very bad solution.

saulspatz
  • 53,131
  • Thanks. Greedy always chooses the best available option. But why in this case the greedy can't perceive that the best option is the center of the small triangle instead of the center of large triangle. – zak100 Apr 06 '20 at 19:47
  • 1
    Because it chooses the best option as if there is only one supply point. That is the center of the big triangle. – saulspatz Apr 06 '20 at 19:49