LFCS seminar by Dr. Justin Ward (Warwick)
Iterative Rounding Algorithms for Stochastic Probing Problems
What 


When 
May 13, 2014 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Contact Name  Ilias Diakonikolas 
Add event to calendar 
vCal iCal 
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 informationtheoretic 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 realworld 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 constantfactor guarantee in the case of a submodular objective function. This talk is based on joint work with Marek Adamczyk and Maxim Sviridenko.