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.
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.