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].
A Stochastic Probing Problem with Applications
Published 2013 in Conference on Integer Programming and Combinatorial Optimization
ABSTRACT
PUBLICATION RECORD
- Publication year
2013
- Venue
Conference on Integer Programming and Combinatorial Optimization
- Publication date
2013-02-24
- Fields of study
Mathematics, Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
- No claims are published for this paper.
CONCEPTS
- No concepts are published for this paper.
REFERENCES
Showing 1-24 of 24 references · Page 1 of 1