a consequence, the dependency on the dimension increases from linear and additive to a singly exponential factor.

### Analysis of the $2k$-clustering {#rad_2k_sec}

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

Just as in the analysis of Algorithm \[drad\_algo\], we divide the merge steps of Algorithm \[rad\_algo\] into phases, such that in each phase the number of remaining clusters is reduced by one fourth. Like in the discrete case, the input points are $(k,\operatorname{opt}_k)$-coverable. However, centers corresponding to an intermediate solution computed by Algorithm \[rad\_algo\] need not be covered by the $k$ balls induced by an optimal solution. As a consequence, we are no longer able to apply Lemma \[volume\_lem\] on the centers as in the discrete case.

To bound the increase of the cost during a single phase, we cover the remaining clusters at the beginning of a phase by a set of overlapping balls. Each of the clusters is completely contained in one of these balls that all have the same radius. Furthermore, the number of remaining 