discrete $k$-center problem.[]{data-label="drad_algo"}

------------------------------------------------------------------------

${\mathcal{C}}_{|X|}:=\left\{\,\{x\}\,|\,x\in X\right\}$ find distinct clusters $A,B\in {\mathcal{C}}_{i+1}$ minimizing $\operatorname{drad}(A\cup B)$\[drad\_algo\_min\] ${\mathcal{C}}_i:=({\mathcal{C}}_{i+1}\setminus\{A,B\})\,\cup\,\{A\cup B\}$ ${\mathcal{C}}_1,\ldots,{\mathcal{C}}_{|X|}$

------------------------------------------------------------------------

Given a finite set $X\subset{\mathbb{R}}^d$ of input points, the algorithm computes hierarchical $k$-clusterings for all values of $k$ between $1$ and $|X|$. We denote them by ${\mathcal{C}}_1,\ldots,{\mathcal{C}}_{|X|}$. Throughout this section, *cost* always means discrete radius cost. $\operatorname{opt}_k$ refers to the cost of an optimal discrete $k$-center clustering of $X\subset{\mathbb{R}}^d$ where $k\in{\mathbb{N}}$ with $k\leq|X|$, i.e. the cost of an optimal solution to Problem \[drad\_prob\].

The following theorem states our result for the discrete $k$-center problem.

\[drad\_result\] Let $X\subset{\mathbb{R}}^d$ be a finite set of points. Then, for all $k\in{\mathbb{N}}$ with $k\leq|X|$, the partition ${\mathcal{C}}_k$ of $X$ into $k$ clusters as computed by Algorithm \[drad\_algo\] satisfies $$\operatorname{cost_{drad}}({\mathcal{C}}_k)<(20d+2\log_2(k)+2)\cdot\operatorname{opt}_k,$$ where $\operatorname{opt}_k$ denotes the cost of an optimal solution to Problem \[drad\_prob\].

Since any cluster $C$ is contained in a ball of radius $\operatorname{drad}(C)$, we have that $X$ is $(k,\operatorname{cost_{drad}}({\mathcal{C}}_k))$-coverable for any $k$-clustering ${\mathcal{C}}_k$ of $X$. It follows, that $X$ is $(k,\operatorname{opt}_k)$-coverable. This fact, as well as the following observation about the greedy strategy of Algorithm \[drad\_algo\], will be used frequently in our analysis..

\[drad\_greedy\_obs\] The cost of all computed clusterings is equal to the discrete radius of 