Stochastic Probing with Applications

David Kalichman

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.

Date
Sep 23, 2022 12:00 PM
Location
MC6029 or Zoom