TY - GEN

T1 - A stochastic probing problem with applications

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

PY - 2013

Y1 - 2013

N2 - We study a general stochastic probing problem defined on a universe V, where each element e ∈ V is "active" independently with probability pe . Elements have weights {we : e ∈ V} and the goal is to maximize the weight of a chosen subset S of active elements. However, we are given only the pe 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: - the set Q of probed elements satisfy an "outer" packing constraint, - 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 [1, 2] and Bayesian mechanism design [3], and can also handle more general constraints. As an application, we obtain the first polynomial-time Ω(1/k)-approximate "Sequential Posted Price Mechanism" under k-matroid intersection feasibility constraints, improving on prior work [3-5].

AB - We study a general stochastic probing problem defined on a universe V, where each element e ∈ V is "active" independently with probability pe . Elements have weights {we : e ∈ V} and the goal is to maximize the weight of a chosen subset S of active elements. However, we are given only the pe 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: - the set Q of probed elements satisfy an "outer" packing constraint, - 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 [1, 2] and Bayesian mechanism design [3], and can also handle more general constraints. As an application, we obtain the first polynomial-time Ω(1/k)-approximate "Sequential Posted Price Mechanism" under k-matroid intersection feasibility constraints, improving on prior work [3-5].

UR - http://www.scopus.com/inward/record.url?scp=84875525295&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875525295&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36694-9_18

DO - 10.1007/978-3-642-36694-9_18

M3 - Conference contribution

AN - SCOPUS:84875525295

SN - 9783642366932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 205

EP - 216

BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings

T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

Y2 - 18 March 2013 through 20 March 2013

ER -