Coverage Maximization with Uniform Query Sizes in Stochastic Settings
We are given a set of items , and a set of users with a parameter . Each user is interested in a subset of items which is unknown to us. Our goal is to find a set of 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--coverage for which the simple Greedy algorithm gives a -approximation. We have the following oracle access to the interest lists. We are given non-negative numbers . At each query, we can provide a sequence of exactly items , and in response we receive a set of users who were interested in at least one of the items in the sequence. Each user selects one of the items in , and gives it to us. The stochastic assumption is that this item is selected proportional to the probability of its location in sequence . For example, if user is interested in items and of the sequence, she will return each of these three items with probabilities and respectively. The question is whether there exists a -approximation for this problem.