A Stochastic Probing Problem with Applications
GuptaAnupam
NagarajanViswanath
1978
<p>We study a general <em>stochastic probing</em> problem defined on a universe <em>V</em>, where each element<em>e</em> ∈ <em>V</em> is “active” independently with probability <em>p</em> <em>e</em> . Elements have weights {<em>w</em> <em>e</em> :<em>e</em> ∈ <em>V</em>} and the goal is to maximize the weight of a chosen subset <em>S</em> of active elements. However, we are given only the <em>p</em> <em>e</em> values—to determine whether or not an element <em>e</em> is active, our algorithm must <em>probe</em> <em>e</em>. If element <em>e</em> is probed and happens to be active, then <em>e</em> must irrevocably be added to the chosen set <em>S</em>; if <em>e</em> is not active then it is not included in <em>S</em>. Moreover, the following conditions must hold in every random instantiation:</p>
<ul>
<li>
<p>the set <em>Q</em> of probed elements satisfy an “outer” packing constraint,</p>
</li>
<li>
<p>the set <em>S</em> of chosen elements satisfy an “inner” packing constraint.</p>
</li>
</ul>
<p>The kinds of packing constraints we consider are intersections of matroids and knapsacks. Our results provide a simple and unified view of results in stochastic matching [1, 2] and Bayesian mechanism design [3], and can also handle more general constraints. As an application, we obtain the first polynomial-time Ω(1/<em>k</em>)-approximate “Sequential Posted Price Mechanism” under <em>k</em>-matroid intersection feasibility constraints, improving on prior work [3-5].</p>