Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS seminar by Dr. Justin Ward (Warwick)

LFCS seminar by Dr. Justin Ward (Warwick)

— filed under:

Iterative Rounding Algorithms for Stochastic Probing Problems

  • Upcoming events
When May 13, 2014
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Contact Name
Add event to calendar vCal

In the stochastic bipartite matching problem, as in the classical version, we must find a maximum weight matching in a given weighted bipartite graph.  However, in the stochastic variant we do not know exactly which edges are present in the input graph.  Rather, we have a probability for each edge, and must ‚Äúprobe" an edge to see if it is present, taking it into the matching if the test succeeds.  A probing algorithm is then simply an adaptive strategy for deciding which sequence of elements to probe.  We measure the performance of a probing algorithm with respect to the expected performance of the optimal probing strategy for a given problem (note that we do not place any computational constraints on the optimal strategy, but rather require it to respect the information-theoretic constraints of the probing model).

In this talk, I will describe a general model capturing stochastic probing problems in which we are given several constraints on both the set of items that may be taken and the set of items that may be probed.  This setting captures several interesting real-world problems, including Internet dating and kidney exchange.  I will present a new algorithm for the general setting that is based on iterative rounding of mathematical programs.  Our algorithm has improved performance in the general stochastic probing setting and gives the first known constant-factor guarantee in the case of a submodular objective function.  This talk is based on joint work with Marek Adamczyk and Maxim Sviridenko.

Document Actions