Streaming Algorithms for Geometric Steiner Forest

Algorithms Seminar
Speaker Name
Robert Krauthgamer
Date and Time
The talk will be virtual on Zoom.
The Zoom link will be emailed to CS faculty/grad students, or contact Jennifer Schmidt (jschmidt at to request it.

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.

Short Biography

Robert Krauthgamer is Professor and Department Head of the Department of Computer Science & Applied Mathematics
at the The Weizmann Institute of Science in Israel.