ALGOTHEORY SEMINAR

Streaming Algorithms for Geometric Steiner Forest

Speaker
Dr. Shaofeng Jiang, Assistant Professor, Peking University
Chaired by
Dr Diptarka CHAKRABORTY, Assistant Professor, School of Computing
  diptarka@comp.nus.edu.sg

  24 Jan 2022 Monday, 04:00 PM to 05:00 PM

 via Zoom

Abstract:
We consider an important generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset X \subseteq R^2, partitioned into k color classes C_1, C_2,..., C_k \subseteq X. The goal is to find a minimum-cost Euclidean graph G such that every color class C_i is connected in G. We study this Steiner forest problem in the streaming setting, where the stream consists of insertions and deletions of points to X. Each input point x \in X arrives with its color color(x) \in [k], and as usual for dynamic geometric streams, the input points are restricted to the discrete grid {0,...,\Delta}^2.

We design 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 a ratio arbitrarily close to the famous Euclidean Steiner ratio \alpha_2 (currently 1.1547 <= \alpha_2 <= 1.214). This approximation guarantee matches the state-of-the-art bound for streaming Steiner tree, i.e., when k=1. Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical Arora-style dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting.

We complement our streaming algorithm for the Steiner forest problem with simple arguments showing that any finite approximation requires \Omega(k) bits of space.

(Based on joint work with Artur Czumaj, Robert Krauthgamer, Pavel VeselĂ˝)


Biodata:
Shaofeng Jiang is an assistant professor at Peking University. Before joining PKU, he worked as an assistant professor at Aalto University, Finland, and prior to that, was a postdoctoral researcher at the Weizmann Institute of Science, Israel. He obtained his Ph.D. from the University of Hong Kong, and bachelor's degree from Shandong University.

Shaofeng's research field is theoretical computer science, and he is interested in algorithms in a broad sense. Currently, he is working on algorithms for massive data sets, approximation algorithms, and online algorithms. Further information can be found at https://shaofengjiang.cn/.