Pass-Efficient Algorithms for Facility Location

Abstract

We present streaming algorithms that use multiple passes for the facility location problem: given a metric space $(X, d)$ consisting of $n$ points, and a facility cost $f_i$ for each $x_i\in X$, find a set $F\subseteq X$ that minimizes the objective function $\sum_{x_i\in F} f_i+\sum_{x_i\in X}d(x_i,F)$, where $d(x_i, C)$ denotes the distance from $x_i$ to the closest point in the set $C$.

Our main result is a $3(\ell-1)$ pass algorithm that outputs a solution to facility location with approximation ratio $O(\ell)$ using an amount of extra space equal to $\tilde{O}(k^* n^{2/\ell})$, where $k^*$ is the number of facilities used by the approximate solution. Our multiple pass algorithm offers a tradeoff between the number of passes and the space used, such that extra space needed by the algorithm falls exponentially with the number of passes. This tradeoff allows much flexibility for fine-tuning resource usage to balance the number of passes with the space used.

This algorithm addresses the need for a small space streaming algorithm for facility location. Using communication complexity results, we show that its parameterization by $k^*$ is necessitated by the existence of families of instances of facility location that require any $\ell$ pass approximation algorithm to use at least $\Omega(n/\ell)$ bits of memory to approximate the cost of the optimum solution.

Back to publications
Back to previous page