License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2021.12
URN: urn:nbn:de:0030-drops-137208
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13720/
McGregor, Andrew ;
Tench, David ;
Vu, Hoa T.
Maximum Coverage in the Data Stream Model: Parameterized and Generalized
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 single-pass 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 single-pass 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 single-pass 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 constant-pass algorithm with an approximation better than e/(e-1) and e^{1-1/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:1--12:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-179-5},
ISSN = {1868-8969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13720},
URN = {urn:nbn:de:0030-drops-137208},
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 |
