Tight bounds for single-pass streaming complexity of the set cover problem

DOI10.1145/2897518.2897576zbMath1373.68250arXiv1603.05715OpenAlexW2300360052MaRDI QIDQ5361872

Sanjeev Khanna, Sepehr Assadi, Yang Li

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

communication complexitystreaming algorithmsset covercovering integer programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (8)

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Fractional Set Cover in the Streaming Model. ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ Online algorithms for the maximum \(k\)-interval coverage problem

This page was built for publication: Tight bounds for single-pass streaming complexity of the set cover problem