Combinatorial Optimization Reading Group - David Kalichman

Title: Stochastic Probing with Applications

Abstract: We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active. If a probed element turns out to be active, then we must include it in our set. In addition, two packing constraints must be satisfied - one for the set of active elements, and another for the set of probed elements. In this talk, I will present a performance guarantee for the greedy algorithm in the unweighted case and an algorithm for the weighted case that uses contention resolution schemes. Finally, I will discuss applications of these algorithms to pricing items in Bayesian auctions and to online dating and kidney exchange problems.