Details

A.1 Omitted Proofs (Details for Lemma 3) Clustering Nets Next, we give a detailed proof of Lemma 4. Proof of Lemma 4. Our objective is to generate a small set of cost vectors that satisfy the desired guarantee. We first define the cost vectors (the reader familiar with the proof sketch from the main body of the submission may skip this and the next paragraph). For each subset U of size O(min(α 22i,α 2+ki), we consider the the subspace ΠU spanned by U. In this subspace we consider (α/2i) p cost(p,A)nets of every ball centered around ΠUpwith radius 60 2i/2 p cost(p,A)for all p P. Such a net has size exp(γ rank(U)ilogα), for some constant γ and there exist at most P 0 exp(γ |U|ilogα) Furthermore, there are at most P 0|U| = P |U|0 such subsets. Now, for every point p, define an exponential sequence α2(1 + α/2i)j for j {0,...log102i}. There exist at most P 0 such sequences and every such sequence consists of at most O(α 1 2i i) many values. We combine every net point in ever ball of every subspace with all values in the exponential sequence to obtain the evaluation for a single candidate center.