University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Maximum Coverage in Sublinear Space, Faster

Maximum Coverage in Sublinear Space, Faster

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

  • UserAnthony Wirth (Melbourne)
  • ClockThursday 27 April 2023, 15:00-16:00
  • HouseArts 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.