Full text  Click to download. 
Citation  Yale
University Technical Report YALEU/DCS/TR1337, November
2005

Author  Kevin Chang

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(\ell1)$ 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 finetuning 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.