Interval selection in data streams: weighted intervals and the insertion-deletion setting

DOI10.4230/LIPICS.FSTTCS.2023.24MaRDI QIDQ6951712zbMATH OpenFDO

Authors Jacques Dark, Adithya Diddapur, Christian Konrad

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2023.24

zbMATH Keywords

insertion-deletion streamsinterval selectionstreaming algorithmsweighted intervals

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• Approximating the Caro-Wei bound for independent sets in graph streams
• Approximation schemes for covering and packing problems in image processing and VLSI
• Communication Complexity
• Independent sets in vertex-arrival streams
• Interval selection in the streaming model
• On streaming algorithms for geometric independent set and clique
• Space-constrained interval selection
• Streaming algorithms for independent sets in sparse hypergraphs
• Streaming and communication complexity of clique approximation
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.

Cited in

(1)

• Interval selection in sliding windows

This page was built for publication: Interval selection in data streams: weighted intervals and the insertion-deletion setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6951712)