= Solution
The optimum radius is a distance from some city to a selected city, so it belongs to
$$
D=\{0\}\cup\{d(u,v):u,v\in V,\ u\ne v\}.
$$
Sort the distinct values of $D$, try them in increasing order, and run part (i)'s greedy procedure with each trial value $r$. Declare a trial successful when all cities are covered using at most $k$ centers; stop a failed trial as soon as a $(k+1)$st center would be selected. The trial $r=r^*$ must succeed by part (i), so the first successful value $\widehat r$ satisfies $\widehat r\leq r^*$. Its output has
$$
\boxed{R\leq2\widehat r\leq2r^*.}
$$
There are $O(n^2)$ candidate distances and $O(n^2)$ work per trial, giving a <polynomial-time algorithm> with <running time> $O(n^4)$, plus sorting. Success at $r$ need not mean that radius $r$ itself is feasible; only the radius-$2r$ guarantee is used.
A faster alternative is the <farthest-first traversal>. Choose any first center, then repeatedly choose a city farthest from its nearest current center until $k$ have been chosen. Let $R$ be the resulting radius. If $R>0$, adjoin a city attaining that distance. At every earlier selection, the maximum distance to the then-current center <set> was at least $R$, so all pairs among these $k+1$ cities are at distance at least $R$. Two belong to the same optimal radius-$r^*$ <closed ball>, giving $R\leq2r^*$ by the <triangle inequality>. If $R=0$, the guarantee is immediate. Maintaining nearest-center distances gives \b[$O(nk)$ distance evaluations] without knowing $r^*$.
Back to article page
