Interval selection in the streaming model

DOI10.1016/j.tcs.2017.08.015zbMath1380.68443arXiv1501.02285OpenAlexW2963282128MaRDI QIDQ1676325

Sergio Cabello, Pablo Pérez-Lantero

Publication date: 6 November 2017

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.02285

zbMATH Keywords

intervalsindependent setapproximation algorithmsdata streamrandom estimationwise independent hash functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

Interval selection in the streaming model, On streaming algorithms for geometric independent set and clique, Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams., Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A derandomization using min-wise independent permutations
• Min-wise independent permutations
• Interval selection in the streaming model
• On graph problems in a semi-streaming model
• A Small Approximately Min-Wise Independent Family of Hash Functions
• Space-Constrained Interval Selection
• Interval scheduling: A survey
• Streaming Algorithms for Independent Sets
• Approximation schemes for covering and packing problems in image processing and VLSI
• Estimating the Efficiency of Backtrack Programs
• Communication Complexity
• Space-Constrained Interval Selection