Pavel Vesely, Charles University

Abstract

We present streaming algorithms for Uniform Facility Location in high-dimensional Euclidean spaces, which compute a constant approximation of the optimal cost in one or a few passes over the input stream while using memory only polynomial (and certainly not exponential) in the dimension. Our algorithms are based on importance sampling of points from the stream such that, informally, points contributing more to the objective are more likely to be sampled than points from "dense clusters", which can be served relatively cheaply. Our sampling procedure relies on consistent hashing (a.k.a. sparse partition) that maps points in R^d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into a small number of distinct buckets. Still, our one-pass algorithm requires space n^epsilon for a given epsilon > 0 affecting the approximation ratio, and it is open how to compute a constant approximation in one pass using space polynomial in the dimension and polylogarithmic in the number of points n.

[Video]