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].

\(\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].