Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 3 / d / ii

The optimum radius is a distance from some city to a selected city, so it belongs toSort 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^{\ast }$ must succeed by part (i), so the first successful value $\hat{r}$ satisfies $\hat{r}\le r^{\ast }$. Its output hasThere 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^{\ast }$ closed ball, giving $R\le 2r^{\ast }$ by the triangle inequality. If $R=0$, the guarantee is immediate. Maintaining nearest-center distances gives $O(nk)$ distance evaluations without knowing $r^{\ast }$.