An improved data stream algorithm for clustering

In the k-center problem for streaming points in d-dimensional metric space, input points are given in a data stream and the goal is to find the k smallest congruent balls whose union covers all input points by examining them. In the single-pass streaming model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited.In this paper, we present a single-pass, (1.8+ε)(1.8+ε)-factor, O(d/ε)O(d/ε)-space data stream algorithm for the Euclidean 2-center problem for any d≥1d≥1. This is the first result with an approximation factor below 2 using O(d/ε)O(d/ε) space for any d. Our algorithm naturally extends to the Euclidean k  -center problem with k>2k>2. We present a single-pass (1.8+ε)(1.8+ε)-factor data stream algorithm for the Euclidean k  -center problem for any d≥1d≥1, which uses O(2k(k+3)!d/ε)O(2k(k+3)!d/ε) space and O(2k(k+2)!d/ε)O(2k(k+2)!d/ε) update time.