Streaming Algorithms for Geometric Steiner Forest

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

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.