Abstract
We present algorithms for the Max Coverage and Max Unique Coverage problems in the data stream model. The input to both problems are m subsets of a universe of size n and a value k ∈ [m]. In Max Coverage, the problem is to find a collection of at most k sets such that the number of elements covered by at least one set is maximized. In Max Unique Coverage, the problem is to find a collection of at most k sets such that the number of elements covered by exactly one set is maximized. These problems are closely related to a range of graph problems including matching, partial vertex cover, and capacitated maximum cut. In the data stream model, we assume k is given and the sets are revealed online. Our goal is to design singlepass algorithms that use space that is sublinear in the input size. Our main algorithmic results are:
 If the sets have size at most d, there exist singlepass algorithms using O(d^{d+1} k^d) space that solve both problems exactly. This is optimal up to polylogarithmic factors for constant d.
 If each element appears in at most r sets, we present single pass algorithms using Õ(k² r/ε³) space that return a 1+ε approximation in the case of Max Coverage. We also present a singlepass algorithm using slightly more memory, i.e., Õ(k³ r/ε⁴) space, that 1+ε approximates Max Unique Coverage. In contrast to the above results, when d and r are arbitrary, any constant pass 1+ε approximation algorithm for either problem requires Ω(ε^{2}m) space but a single pass O(ε^{2}mk) space algorithm exists. In fact any constantpass algorithm with an approximation better than e/(e1) and e^{11/k} for Max Coverage and Max Unique Coverage respectively requires Ω(m/k²) space when d and r are unrestricted. En route, we also obtain an algorithm for a parameterized version of the streaming Set Cover problem.
BibTeX  Entry
@InProceedings{mcgregor_et_al:LIPIcs.ICDT.2021.12,
author = {McGregor, Andrew and Tench, David and Vu, Hoa T.},
title = {{Maximum Coverage in the Data Stream Model: Parameterized and Generalized}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {12:112:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771795},
ISSN = {18688969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13720},
URN = {urn:nbn:de:0030drops137208},
doi = {10.4230/LIPIcs.ICDT.2021.12},
annote = {Keywords: Data streams, maximum coverage, maximum unique coverage, set cover}
}
Keywords: 

Data streams, maximum coverage, maximum unique coverage, set cover 
Collection: 

24th International Conference on Database Theory (ICDT 2021) 
Issue Date: 

2021 
Date of publication: 

11.03.2021 