Streaming Algorithms for Geometric Steiner Forest (Shaofeng Jiang)

Abstract

We consider a natural generalization of theSteiner tree problem, the /emph{Steiner forest problem}, in the Euclideanplane: the input is a multiset X /subseteq /mathbb{R}^2, partitioned into kcolor classes C_1, C_2, /ldots, C_k /subseteq X. The goal is to find aminimum-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 streamconsists of insertions and deletions of points to X. Each input point x/in Xarrives with its color /mathrm{col}(x) /in [k], and as usual for dynamicgeometric streams, the input points are restricted to the discrete grid /{0,/ldots, /Delta/}^2.

 

We design a single-pass streaming algorithmthat uses poly(k /cdot /log/Delta) space and time, and estimates the cost of anoptimal Steiner forest solution within ratio arbitrarily close to the famousEuclidean Steiner ratio alpha_2 (currently 1.1547 /le /alpha_2 /le 1.214). Ourapproach relies on a novel combination of streaming techniques, like samplingand linear sketching, with the classical dynamic-programming framework forgeometric optimization problems, which usually requires large memory and has sofar not been applied in the streaming setting.

Time

2021-06-18  14:30-15:00   

Speaker

Shaofeng Jiang, Peking University

Room

Guangdong Hotel Shanghai