Submodular Stochastic Probing with Prices
Ben Chugg, Takanori Maehara · 2019
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 ($\mathcal{N},\mathcal{I}_{\mathrm{i}\mathrm{n}}$) and ($\mathcal{N},\mathcal{I}_{\mathrm{o}\mathrm{u}\mathrm{t}}$) where each$e\in \mathcal{N}$is active with probability$p_{e}$. To discover whether an element$e$is active, it must be probed by paying the price$\Delta_{\mathrm{e}}$. If an element is probed and is active, then it is irrevocably added to the solution. Moreover, at all times, the set of probed elements must lie in$\mathcal{I}_{\text{out}}$, and the solution (the set of probed and active elements) must lie in$\mathcal{I}_{\text{in}}$. The goal is to maximize a submodular set function$f$minus the cost of the probes. We give a bicriteria approximation algorithm to the online version of this problem, in which the elements are shown to the algorithm in a possibly adversarial order. Our results translate to state-of-the-art approximations for the traditional (online) stochastic probing problem.