3b7ba46201bf15e5c3935272afae50db-Supplemental-Conference.pdf

By making the appropriate changes to the proofs of Lemma B.3 and Lemma B.4, we get These two lemmas immediately imply the following generalization of Lemma B.5. The upper bound on cost(σ) given in Lemma B.6 can be generalized by noticing that cost(σ, C The lower bound on opt(U) given in Lemma B.10 holds for ρ-metric spaces with no modifications. By making the appropriate modifications to the proof of Theorem C.1, we can extend this theorem to In particular, we can obtain a proof of Theorem A.5 by taking the proof of Theorem C.1 and adding extra ρ factors whenever the triangle inequality is applied. We first prove Lemma B.1, which shows that the sizes of the sets U By Lemma B.2, we get that Henceforth, we fix some positive ξ and sufficiently large α such that Lemma B.3 holds. By now applying Lemma B.4 it follows that µ Lower Bounding opt(U) (Lemma B.10): Let r denote log For the rest of this subsection we fix an arbitrary S U of size k.