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

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.