We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P sube ℝ2 and an opening cost f ∊ ℝ+, and we want to find a set of facilities F ⊆ ℝ2 that minimizes where d(p, q) is the Euclidean distance between p and q. We obtain two main results: A (1 + ε)-approximation algorithm with running time which is (n log2 n log log n) for any constant ε. The first (1 + ε)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i.e., when the stream consists of insert and delete operations of points from a discrete space {1, …, Δ}2. The streaming algorithm uses space. Our PTAS is significantly faster than any previously known (1 + ε)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + ε)-approximation algorithm for the cost of the facility location problem with polylogarithmic space, and it resolves an open problem in the streaming area. Both algorithms are based on a novel and simple decomposition of an input point set P into small subsets Pi, such that: the cost of solving the facility location problem for each Pi is small (which means that for each Pi one needs to open only a small, polylogarithmic number of facilities), Σi OPT(Pi) ≤ (1 + ε) · OPT(P), where for a point set P, OPT(P) denotes the cost of an optimal solution for P. The decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm.

We develop a new k-means clustering algorithm for data streams, which we call StreamKM++. Our algorithm computes a small weighted sample of the data stream and solves the problem on the sample using the k-means++ algorithm [1]. To compute the small sample, we propose two new techniques. First, we use a non-uniform sampling approach similar to the k-means++ seeding procedure to obtain small core-sets from the data stream. This construction is rather easy to implement and, unlike other coreset constructions, its running time has only a low dependency on the dimensionality of the data. Second, we propose a new data structure which we call a coreset tree. The use of these coreset trees significantly speeds up the time necessary for the non-uniform sampling during our coreset construction. We compare our algorithm experimentally with two well-known streaming implementations (BIRCH [16] and StreamLS [4, 9]). In terms of quality (sum of squared errors), our algorithm is comparable with StreamLS and significantly better than BIRCH (up to a factor of 2). In terms of running time, our algorithm is slower than BIRCH. Comparing the running time with StreamLS, it turns out that our algorithm scales much better with increasing number of centers. We conclude that, if the first priority is the quality of the clustering, then our algorithm provides a good alternative to BIRCH and StreamLS, in particular, if the number of cluster centers is large. We also give a theoretical justification of our approach by proving that our sample set is a small coreset in low dimensional spaces.

In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.