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

## Maximum Coverage in Sublinear Space, FasterAdd 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:Note that ex-directory lists are not shown. |
## Other listsMet and Mat Seminar Series EPS - College Research Teas SoCS PhD Research Training Sessions## Other talksPlasmonic and photothermal properties of TiN nanomaterials Quantum-Enhanced Interferometry hunting in the Dark Universe: How Gravitatioanl-wave detector technology can be (ab)used for other mysteries in fundamental physics. Towards the next generation of hazardous weather prediction: observation uncertainty and data assimilation The tragic destiny of Mileva Marić Einstein TBA The Electron-Ion Collider |