The Library
Streaming algorithms for geometric Steiner forest
Tools
Tools
Tools
Czumaj, Artur, Jiang, Shaofeng H.-C., Krauthgamer, Robert and Veselý, Pavel (2022) Streaming algorithms for geometric Steiner forest. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Paris, France, 04-08 Jul 2022. Published in: Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) pp. 1-20. ISBN 9783959772358. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2022.47
|
PDF
WRAP-Streaming-algorithms-for-geometric-Steiner-forest-Czumaj-22.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (911Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.47
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 ⊆ R^2, partitioned into k color classes C1, C2, . . . , Ck ⊆ 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 ∈ X arrives with its color color(x) ∈ [k], and as usual for dynamic geometric streams, the input is restricted to the discrete grid {0, . . . , ∆}^2.
We design a single-pass streaming algorithm that uses poly(k · log ∆) 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.
| Item Type: | Conference Item (Paper) | |||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > T Technology (General) |
|||||||||||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Machine theory -- Mathematical models, Computational complexity, Steiner systems , Computer algorithms, Dynamic programming | |||||||||||||||||||||||||||||||||||||||
| Journal or Publication Title: | Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | |||||||||||||||||||||||||||||||||||||||
| Publisher: | LIPics | |||||||||||||||||||||||||||||||||||||||
| ISBN: | 9783959772358 | |||||||||||||||||||||||||||||||||||||||
| ISSN: | 1868-8969 | |||||||||||||||||||||||||||||||||||||||
| Official Date: | 28 July 2022 | |||||||||||||||||||||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||||||||||||||||||||
| Page Range: | pp. 1-20 | |||||||||||||||||||||||||||||||||||||||
| Article Number: | 47 | |||||||||||||||||||||||||||||||||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2022.47 | |||||||||||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||||||||||||||||||||
| Access rights to Published version: | Open Access | |||||||||||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||||||||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||||||||||||||||||||||||||
| Title of Event: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | |||||||||||||||||||||||||||||||||||||||
| Type of Event: | Conference | |||||||||||||||||||||||||||||||||||||||
| Location of Event: | Paris, France | |||||||||||||||||||||||||||||||||||||||
| Date(s) of Event: | 04-08 Jul 2022 | |||||||||||||||||||||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
