We already have by Theorem REF  that \(d_{EM}(M_{i-\lambda },R_{i-\lambda }) \le \epsilon \text{\footnotesize \textsf {OPT}}_k(P) \le \epsilon \bar{g}(P,w,C)\)  for any set \(C\)  of size \(k\) . Also, by Theorem REF  we have the \(S_i\)  is an \((k,\epsilon )\) -coreset for \(P \setminus R_{i-\lambda }\) . This is because (in the statement of Theorem REF ) we are required to carry out the construction of Algorithm  using \(m \ge \frac{ck(t+\beta )}{\varepsilon ^2}\left(d\log t+\log (\beta k)+\log \left(\frac{1}{\delta }\right) \right)\)  where \(t = \alpha / \psi \) . It was shown in Lemma REF  that \(\psi = (\epsilon /r)^r\) . We are using the \((O(1),O(\log (\frac{1}{\epsilon }) \log n))\) -approximation \(\mathcal {B}\) , and in [1]} it is shown that \(d = O( \log n)\)  for \(k\) -median in a \(\rho \) -metric space. So therefore the minimal possible value of \(m\)  that satisfies the hypotheses of the theorem is \(O(\frac{k(\epsilon ^{-r}+\log n )}{\varepsilon ^2}\left(\log n\log \epsilon ^{-r} +\log ( k \log n)+\log \left(\frac{1}{\delta }\right) \right) )\) . Simplifying notation, this is \(O(\epsilon ^{-O(1)} k \log n (\log n + \log k + \log \frac{1}{\delta }))\) .
