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

Assume the standard nonempty instance convention $1\le k\le n$, and set $d(v,v)=0$. Start with no centers. Pick any city still farther than $2r^{\ast }$ from every selected center, add it as a center, and mark every city within distance $2r^{\ast }$ of it as covered. Stop when all cities are covered.

Distinct chosen centers have pairwise distance greater than $2r^{\ast }$. Fix an optimal set of $k$ centers and assign each city to one optimal center within distance $r^{\ast }$. Two cities assigned to the same center have distance at most $2r^{\ast }$ by the triangle inequality. Thus no two chosen centers can be assigned to that same optimal center. The pigeonhole principle shows that the greedy procedure selects at most $k$ centers and has radius at most $2r^{\ast }$. 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^{\ast }=0$. It is the packing bound underlying the metric k-center problem.

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