Streaming Algorithms for Geometric Steiner Forest
I will discuss the Steiner forest problem in the Euclidean plane, where the input is a multiset of points, partitioned into k color classes, and the goal is to find a minimum-cost Euclidean graph G such that every color class is connected. We study this problem in dynamic streams, where the input is provided by a stream of insertions and deletions of colored points from the discrete grid [\Delta]^2.
Our main result is a single-pass streaming algorithm that uses poly(k \log\Delta) space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio $\alpha_2$ (currently $1.1547 \leq \alpha_2 \leq 1.214$). Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting. I will also discuss possible directions for future work.
Joint work with Artur Czumaj, Shaofeng H.-C. Jiang, and Pavel Vesely.
Robert Krauthgamer is Professor and Department Head of the Department of Computer Science & Applied Mathematics
at the The Weizmann Institute of Science in Israel.