2026-07-23T13:24:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19397 2024-03-06T11:03:56Z ddc:004 open_access

Interval Selection in Data Streams: Weighted Intervals and the Insertion-Deletion Setting Dark, Jacques Diddapur, Adithya Konrad, Christian Streaming Algorithms Interval Selection Weighted Intervals Insertion-deletion Streams We study the Interval Selection problem in data streams: Given a stream of n intervals on the line, the objective is to compute a largest possible subset of non-overlapping intervals using O(|OPT|) space, where |OPT| is the size of an optimal solution. Previous work gave a 3/2-approximation for unit-length and a 2-approximation for arbitrary-length intervals [Emek et al., ICALP'12]. We extend this line of work to weighted intervals as well as to insertion-deletion streams. Our results include: 1) When considering weighted intervals, a (3/2+ε)-approximation can be achieved for unit intervals, but any constant factor approximation for arbitrary-length intervals requires space Ω(n). 2) In the insertion-deletion setting where intervals can both be added and deleted, we prove that, even without weights, computing a constant factor approximation for arbitrary-length intervals requires space Ω(n), whereas in the weighted unit-length intervals case a (2+ε)-approximation can be obtained. Our lower bound results are obtained via reductions to the recently introduced Chained-Index communication problem, further demonstrating the strength of this problem in the context of streaming geometric independent set problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacques Dark and Adithya Diddapur and Christian Konrad 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.24 urn:nbn:de:0030-drops-193976 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode