# zbMATH — the first resource for mathematics

A stochastic probing problem with applications. (English) Zbl 1372.90091
Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 205-216 (2013).
Summary: We study a general stochastic probing problem defined on a universe $$V$$, where each element $$e \in V$$ is “active” independently with probability $$p_e$$. Elements have weights $$\{w_e: e \in V\}$$ and the goal is to maximize the weight of a chosen subset $$S$$ of active elements. However, we are given only the $$p_e$$ values-to determine whether or not an element $$e$$ is active, our algorithm must probe $$e$$. If element $$e$$ is probed and happens to be active, then $$e$$ must irrevocably be added to the chosen set $$S$$; if $$e$$ is not active then it is not included in $$S$$. Moreover, the following conditions must hold in every random instantiation:
$$\bullet$$ the set $$Q$$ of probed elements satisfy an “outer” packing constraint,
$$\bullet$$ the set $$S$$ of chosen elements satisfy an “inner” packing constraint.
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 [N. Chen et al., Lect. Notes Comput. Sci. 5555, 266–278 (2009; Zbl 1247.05237), N. Bansal et al., Algorithmica 63, No. 4, 733–762 (2012; Zbl 1254.05145)] and Bayesian mechanism design [S. Chawla et al., Proceedings of the 42nd annual ACM symposium on theory of computing, STOC 2010, New York, NY: ACM, 311–320 (2010; Zbl 1293.91078)], and can also handle more general constraints. As an application, we obtain the first polynomial-time $$\Omega (\frac{1}{k})$$-approximate “sequential posted price mechanism” under $$k$$-matroid intersection feasibility constraints, improving on prior work [S. Chawla et al. (loc. cit.); Q. Yan, Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011. Philadelphia, PA: SIAM; New York, NY: ACM, 710–719 (2011; Zbl 1377.91108); R. Kleinberg and S. M. Weinberg, Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY: ACM, 123–136 (2012; Zbl 1286.60037)].
For the entire collection see [Zbl 1258.90003].

##### MSC:
 90C27 Combinatorial optimization 90C15 Stochastic programming 91B26 Auctions, bargaining, bidding and selling, and other market models
Full Text: