center selection problem: Simple greedy algorithm

Question

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"?

Some body please guide me how by adding centers we can reduce the covering radius?

Zulfi.

Answer 1

Given a set of points, the task is to find a set of centers minimizing the covering radius, defined below. The centers themselves could be arbitrary points in space, or sometimes must be selected among the points or among a set of potential centers.

The covering radius is the minimum $r$ such that each point in the set is at distance at most $r$ from a center. Clearly, adding centers can only reduce the radius, and in general it does. As a very extreme examples, given $n$ distinct points, for any $n-1$ centers that we choose, the covering radius will be positive, while if we take all the points as centers, the covering radius drops to zero.

As another example, consider three points on the real line at locations $-1,0,1$. The best choice for a single center is $0$, with covering radius $1$. The best choice for two centers is $-1/2,1/2$, with covering radius $1/2$. However, if we first put a center at $0$, no choice for the second center will reduce the covering radius.