Streaming Algorithms for Geometric Steiner Forest

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493442" target="_blank" >RIV/00216208:11320/24:10493442 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_8m-4DeLtv" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_8m-4DeLtv</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3663666" target="_blank" >10.1145/3663666</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Streaming Algorithms for Geometric Steiner Forest

Popis výsledku v původním jazyce

We consider a generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset X subset of R2, partitioned into k color classes C1,. .. , C k subset of X . The goal is to find a minimum-cost Euclidean graph G such that every color class C 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 is an element of X arrives with its color color(x) is an element of [k], and as usual for dynamic geometric streams, the input is restricted to the discrete grid {1, ... , Delta }2. We design a single-pass streaming algorithm that uses poly(k &lt;middle dot&gt; 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 a 2 (currently 1.1547 &lt;= a 2 &lt;= 1.214). This approximation guarantee matches the state-of-the-art bound for streaming Steiner tree, i.e., when k = 1, and it is a major open question to improve the ratio to 1 + &amp; even for this special case. 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 so far has not been applied in the streaming setting. We complement our streaming algorithm for the Steiner forest problem with simple arguments showing that any finite multiplicative approximation requires Omega (k) bits of space.

Název v anglickém jazyce

Streaming Algorithms for Geometric Steiner Forest

Popis výsledku anglicky

We consider a generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset X subset of R2, partitioned into k color classes C1,. .. , C k subset of X . The goal is to find a minimum-cost Euclidean graph G such that every color class C 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 is an element of X arrives with its color color(x) is an element of [k], and as usual for dynamic geometric streams, the input is restricted to the discrete grid {1, ... , Delta }2. We design a single-pass streaming algorithm that uses poly(k &lt;middle dot&gt; 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 a 2 (currently 1.1547 &lt;= a 2 &lt;= 1.214). This approximation guarantee matches the state-of-the-art bound for streaming Steiner tree, i.e., when k = 1, and it is a major open question to improve the ratio to 1 + &amp; even for this special case. 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 so far has not been applied in the streaming setting. We complement our streaming algorithm for the Steiner forest problem with simple arguments showing that any finite multiplicative approximation requires Omega (k) bits of space.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

1549-6333

Svazek periodika

20

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

28

Kód UT WoS článku

001356761000007

EID výsledku v databázi Scopus

2-s2.0-85207020419