Semi-streaming set cover

DOI10.1145/2957322MaRDI QIDQ4962638zbMATH OpenOpenAlexFDO

Authors Yuval Emek, Adi Rosén

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsset coverstreaming algorithms

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph $G=(V,E)$ whose edges arrive one-by-one and the goal is to construct an edge cover $FsubseteqE$ with the objective of minimizing the cardinality (or cost in the weighted case) of $F$. We consider a parameterized relaxation of this problem, where given some $0leqepsilon<1$, the goal is to construct an edge $(1-epsilon)$-cover, namely, a subset of edges incident to all but an $epsilon$-fraction of the vertices (or their benefit in the weighted case). The key limitation imposed on the algorithm is that its space is limited to (poly)logarithmically many bits per vertex. Our main result is an asymptotically tight trade-off between $epsilon$ and the approximation ratio: We design a semi-streaming algorithm that on input graph $G$, constructs a succinct data structure $mathcalD$ such that for every $0leqepsilon<1$, an edge $(1-epsilon)$-cover that approximates the optimal edge mbox{($1$-)cover} within a factor of $f(epsilon,n)$ can be extracted from $mathcalD$ (efficiently and with no additional space requirements), where [ f(epsilon, n) = left{ �egin{array}{ll} O (1 / epsilon), & ext{if } epsilon > 1 / sqrt{n} \ O (sqrt{n}), & ext{otherwise} end{array} ight. , . ] In particular for the traditional set cover problem we obtain an $O(sqrtn)$-approximation. This algorithm is proved to be best possible by establishing a family (parameterized by $epsilon$) of matching lower bounds.

Recommendations

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

Cited in

(12)

• Better streaming algorithms for the maximum coverage problem
• scientific article; zbMATH DE number 6696496 (Why is no real title available?)
• Streaming algorithms for independent sets in sparse hypergraphs
• Incidence geometries and the pass complexity of semi-streaming set cover
• Set cover in sub-linear time
• Tight bounds for single-pass streaming complexity of the set cover problem
• Fractional set cover in the streaming model
• Online disjoint set cover without prior knowledge
• Semi-streaming set cover (extended abstract)
• Tight bounds for single-pass streaming complexity of the set cover problem
• Approximate F₂-Sketching of Valuation Functions
• Maximum coverage in the data stream model: parameterized and generalized

This page was built for publication: Semi-streaming set cover

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