Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

DOI10.1137/1.9781611974331.ch94zbMath1409.68135arXiv1507.04645OpenAlexW2952295827MaRDI QIDQ4575677

Amit Chakrabarti, Anthony Wirth

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Unnamed Item ⋮ Fractional Set Cover in the Streaming Model. ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem

This page was built for publication: Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover