Incidence geometries and the pass complexity of semi-streaming set cover

DOI10.1137/1.9781611974331.CH94MaRDI QIDQ4575677zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: Set cover, over a universe of size $n$, may be modelled as a data-streaming problem, where the $m$ sets that comprise the instance are to be read one by one. A semi-streaming algorithm is allowed only $O(n,mathrmpolylogn,logm)$ space to process this stream. For each $pge1$, we give a very simple deterministic algorithm that makes $p$ passes over the input stream and returns an appropriately certified $(p+1)n^{1/(p+1)}$-approximation to the optimum set cover. More importantly, we proceed to show that this approximation factor is essentially tight, by showing that a factor better than $0.99,n^{1/(p+1)}/(p+1{)}^2$ is unachievable for a $p$-pass semi-streaming algorithm, even allowing randomisation. In particular, this implies that achieving a $Theta(logn)$-approximation requires $Omega(logn/loglogn)$ passes, which is tight up to the $loglogn$ factor. These results extend to a relaxation of the set cover problem where we are allowed to leave an $varepsilon$ fraction of the universe uncovered: the tight bounds on the best approximation factor achievable in $p$ passes turn out to be $Thet{a}_p(min{n}^{1/(p+1)},varepsilo{n}^{-1/p})$. Our lower bounds are based on a construction of a family of high-rank incidence geometries, which may be thought of as vast generalisations of affine planes. This construction, based on algebraic techniques, appears flexible enough to find other applications and is therefore interesting in its own right.

Recommendations

• Tight bounds for single-pass streaming complexity of the set cover problem
• Semi-streaming set cover
• Tight bounds for single-pass streaming complexity of the set cover problem
• Semi-streaming set cover (extended abstract)
• scientific article; zbMATH DE number 6905172

Cited in

(9)

• scientific article; zbMATH DE number 7651147 (Why is no real title available?)
• Better streaming algorithms for the maximum coverage problem
• Semi-streaming set cover
• Approximate F_2-Sketching of Valuation Functions
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Fractional set cover in the streaming model
• Tight bounds for single-pass streaming complexity of the set cover problem
• Semi-streaming set cover (extended abstract)
• 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

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