On the complexity of approximation streaming algorithms for the k-center problem

摘要: We study approximation streaming algorithms for the k- center problem in fixed dimensional Euclidean space. Given an integer k ≥ 1 and a set S of n points d-dimensional space, k-center is to cover those with congruent balls smallest possible radius. For any Ɛ > 0, we devise O( k/Ɛd)-space (1 + Ɛ)-approximation algorithm problem, prove that updating time O(k/Ɛd log k) 2O(k1-1/d/Ɛd). On other hand, Ɛ)- must use Ω(k/Ɛ(d-1)/2)-bits memory. Our obtained by first designing off-line (1+Ɛ)-approximation O(n 2O(k1-1/d/Ɛd) complexity, then applying this repeatedly sketch input data stream. If fixed, our improves best-known Agarwal Procopiuc [1] has (k/Ɛ)O(k1-1/d) complexity. approximate different from another Har-Peled [16], which maintains core size O(k/Ɛd), but does not provide solution small 0.