Submodular Stochastic Probing with Prices
share
We introduce Stochastic Probing with Prices (SPP), a variant of the Stochastic Probing (SP) model in which we must pay a price to probe an element. A SPP problem involves two set systems (N,I_in) and (N,I_out) where each e∈ N is active with probability p_e. To discover whether e is active, it must be probed by paying the price Δ_e. If it is probed and active, then it is irrevocably added to the solution. Moreover, at all times, the set of probed elements must lie in I_out, and the solution (the set of probed and active elements) must lie in I_in. The goal is to maximize a set function f minus the cost of the probes. We show this problem can be approximately solved via multilinear relaxation and contention resolution schemes. If I_in and I_out admit (b,c_in) and (b,c_out) contention resolution schemes, we give a {c_out c_in,c_out+c_in-1}α(b)-approximation to online SPP, where α(b)=1-e^-b if f is monotone, and be^-b otherwise. These results apply in the online version of the problem: The elements are presented in an arbitrary (and potentially adversarial) order. In the special case when I_in and I_out are the intersection of k and ℓ matroids, we demonstrate that the optimal value for b is 1/2(z+2-√(z(z+4))) when f is monotone, and z+1-W(ze^z+1) when f is non-monotone, where z=k+ℓ and W is the lambert W function. Our results also provide state-of-the-art approximations for online SP when f is monotone, and provide the first approximation to online, adversarial SP when f is non-monotone. Finally, we demonstrate that when f is modular there exists an α-approximation to SP only if there exists an α-approximation to SPP.
READ FULL TEXT