# Coverage Maximization with Uniform Query Sizes in Stochastic Settings

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
We are given a set of items $I$, and a set of users $U$ with a parameter $k$. Each user $u \in U$ is interested in a subset of items $I_u$ which is unknown to us. Our goal is to find a set of $k$ items to maximize the number of users interested in at least of these items. Please note that if we had direct access to interest subsets of each user, the problem was equivalent to max-$k$-coverage for which the simple Greedy algorithm gives a $(1-\frac{1}{e})$-approximation. We have the following oracle access to the interest lists. We are given $k$ non-negative numbers $p_1, p_2, \cdots, p_k$. At each query, we can provide a sequence of exactly $k$ items $S=$, and in response we receive a set of users $A$ who were interested in at least one of the items in the sequence. Each user $a \in A$ selects one of the items in $I_a \cap S$, and gives it to us. The stochastic assumption is that this item is selected proportional to the probability of its location in sequence $S$. For example, if user $a$ is interested in items $i_2, i_5,$ and $i_8$ of the sequence, she will return each of these three items with probabilities $\frac{p_2}{p_2+p_5+p_8}, \frac{p_5}{p_2+p_5+p_8},$ and $\frac{p_8}{p_2+p_5+p_8}$ respectively. The question is whether there exists a $(1-\frac{1}{e})$-approximation for this problem.