= Solution
Assume the standard nonempty instance convention $1\leq k\leq n$, and set $d(v,v)=0$. Start with no centers. Pick any city still farther than $2r^*$ from every selected center, add it as a center, and mark every city within distance $2r^*$ of it as covered. Stop when all cities are covered.
Distinct chosen centers have pairwise distance greater than $2r^*$. Fix an optimal <set> of $k$ centers and assign each city to one optimal center within distance $r^*$. Two cities assigned to the same center have distance at most $2r^*$ by the <triangle inequality>. Thus no two chosen centers can be assigned to that same optimal center. The <pigeonhole principle> shows that \b[the greedy procedure selects at most $k$ centers and has radius at most $2r^*$]. If fewer than $k$ are selected, add arbitrary distinct cities; this cannot worsen the radius.
With the supplied radius, a straightforward implementation updates coverage in $O(n)$ time per selected center, hence takes $O(nk)$ distance tests. The argument also handles $r^*=0$. It is the packing bound underlying the <metric k-center problem>.
Back to article page
