Coverage Maximization with Uniform Query Sizes in Stochastic Settings

From himtp
Jump to: navigation, search

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=<i_1, i_2, \cdots, i_k>, 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.