Optimal Dynamic Parameterized Subset Sampling

Abstract

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set, S, of n items, where each item, x, has a non-negative integer weight, w(x). Given a pair of query parameters, (α, β), each of which is a non-negative rational number, a parameterized subset sampling query on S seeks to return a subset T ⊆ S such that each item x∈ S is selected in T, independently, with probability p_x(α, β) which is the minimum between 1 and w(x) / (α \cdot W + β), where W is the total weight of the items in S. More specifically, the DPSS problem is defined in a dynamic setting, where the item set, S, can be updated with insertions of new items..