2021/02/16 by Andrew McGregor, David Tench, McGregor, Andrew +3 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2102.08476
Conference version to appear at ICDT 2021
arxiv created 2021/02/16 · arxiv updated 2021/02/18
We present algorithms for the Max-Cover and Max-Unique-Cover 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-Cover, 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-Cover, 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. 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(dd+1 kd) 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 O(k2 r/ε3) space that return a 1+ε approximation in the case of Max-Cover. We also present a single-pass algorithm using slightly more memory, i.e., O(k3 r/ε4) space, that 1+ε approximates Max-Unique-Cover. In contrast to the above results, when d and r are arbitrary, any constant pass 1+ε approximation algorithm for either problem requires Ω(ε-2m) space but a single pass O(ε-2mk) space algorithm exists. In fact any constant-pass algorithm with an approximation better than e/(e-1) and e1-1/k for Max-Cover and Max-Unique-Cover respectively requires Ω(m/k2) space when d and r are unrestricted. En route, we also obtain an algorithm for a parameterized version of the streaming Set-Cover problem.