120c9ab5c58ba0fa9dd3a22ace1de245-Supplemental-Conference.pdf

Our objective is to generate a small set of cost vectors that satisfy the desired guarantee. We combine every net point in ever ball of every subspace with all values in the exponential sequence toobtain theevaluation forasingle candidate center. Combined with the bounds onU, this yields the desired size. What remains tobeshown isthat the thus constructed cost vectors satisfy the guarantee ofa (α,k)-clusteringnet. Tosimplify the calculations, we use the bound cost(p,S) 2icost(p,A); the result then follows by folding in the constant factor in the definitionofα.