2026-08-06T11:08:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13720 2024-03-06T10:52:31Z ddc:004 open_access

Maximum Coverage in the Data Stream Model: Parameterized and Generalized McGregor, Andrew Tench, David Vu, Hoa T. Data streams maximum coverage maximum unique coverage set cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew McGregor and David Tench and Hoa T. Vu 2021 Is Part Of LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2021.12 urn:nbn:de:0030-drops-137208 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.12 eng https://creativecommons.org/licenses/by/4.0/legalcode