Maximum Coverage in Sublinear Space, Faster

Add to your list(s) Download to your calendar using vCal

• Anthony Wirth (Melbourne)
• Thursday 27 April 2023, 15:00-16:00
• Arts LR6.

If you have a question about this talk, please contact Dr Richard Mycroft.

Given a collection of m sets from a universe U, the Maximum Set Coverage problem consists of finding k sets whose union has largest cardinality. This problem is NP-Hard, but the solution can be approximated by a polynomial time algorithm up to a factor 1−1/e. However, this algorithm does not scale well with the input size. In a streaming context, practical high-quality solutions are found, but with space complexity that scales linearly with respect to the size of the universe |U|. However, one randomized streaming algorithm has been shown to produce a 1−1/e−ε approximation of the optimal solution with a space complexity that scales only poly-logarithmically with respect to m and |U|. In order to achieve such a low space complexity, the authors used a technique called subsampling, based on independent-wise hash functions. This article focuses on this sublinear-space algorithm and introduces methods to reduce the time cost of subsampling. We first show how to accelerate by several orders of magnitude without altering the space complexity, number of passes and approximation quality of the original algorithm. Secondly, we derive a new lower bound for the probability of producing a 1−1/e−ε approximation using only pairwise independence: 1 − 4/(ck log m) compared to the original 1−2e/m^(ck/6). Although the theoretical approximation guarantees are weaker, for large streams, our algorithm performs well in practice and present the best time-space-performance trade-off for maximum coverage in streams.

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Arts LR6
• Combinatorics and Probability seminar
• School of Mathematics events

Note that ex-directory lists are not shown.