Streaming Algorithms for Geometric Steiner Forest
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455634" target="_blank" >RIV/00216208:11320/22:10455634 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.ICALP.2022.47" target="_blank" >https://doi.org/10.4230/LIPIcs.ICALP.2022.47</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2022.47" target="_blank" >10.4230/LIPIcs.ICALP.2022.47</a>
Alternative languages
Result language
angličtina
Original language name
Streaming Algorithms for Geometric Steiner Forest
Original language description
We consider an important generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset X SUBSET OF OR EQUAL TO ℝ2, partitioned into k color classes C1, C2,..., Ck SUBSET OF OR EQUAL TO X. The goal is to find a minimum-cost Euclidean graph G such that every color class Ci 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 ELEMENT OF X arrives with its color color(x) ELEMENT OF [k], and as usual for dynamic geometric streams, the input is restricted to the discrete grid {0,..., INCREMENT }2. We design a single-pass streaming algorithm that uses poly(k . log INCREMENT ) space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio α2 (currently 1.1547 <= α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 Ω(k) bits of space. (C) Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý; licensed under Creative Commons License CC-BY 4.0
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-235-8
ISSN
1868-8969
e-ISSN
—
Number of pages
20
Pages from-to
—
Publisher name
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Place of publication
Dagstuhl, Germany
Event location
Paříž, Francie
Event date
Jul 4, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—