Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Optimal Dynamic Parameterized Subset Sampling
Junhao Gan, Seeun William Umboh, Hanzhi Wang +2
In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~, of~ items, where each item,~, has a…
cs.DS2024
Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
Philip Cervenjak, Junhao Gan, Seeun William Umboh +1
We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of elements, a collection of subsets of this universe,…
cs.DS2024
Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
Amit Chakrabarti, Andrew McGregor, Anthony Wirth
The maximum coverage problem is to select sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider -appro…