Abstract
Consider a kidneyexchange application where we want to find a maxmatching in a random graph. To find whether an edge e exists, we need to perform an expensive test, in which case the edge e appears independently with a known probability p_e. Given a budget on the total cost of the tests, our goal is to find a testing strategy that maximizes the expected maximum matching size.
The above application is an example of the stochastic probing problem. In general the optimal stochastic probing strategy is difficult to find because it is adaptive  decides on the next edge to probe based on the outcomes of the probed edges. An alternate approach is to show the adaptivity gap is small, i.e., the best nonadaptive strategy always has a value close to the best adaptive strategy. This allows us to focus on designing nonadaptive strategies that are much simpler. Previous works, however, have focused on Bernoulli random variables that can only capture whether an edge appears or not. In this work we introduce a multivalue stochastic probing problem, which can also model situations where the weight of an edge has a probability distribution over multiple values.
Our main technical contribution is to obtain (near) optimal bounds for the (worstcase) adaptivity gaps for multivalue stochastic probing over prefixclosed constraints. For a monotone submodular function, we show the adaptivity gap is at most 2 and provide a matching lower bound. For a weighted rank function of a kextendible system (a generalization of intersection of k matroids), we show the adaptivity gap is between O(k log k) and k. None of these results were known even in the Bernoulli case where both our upper and lower bounds also apply, thereby resolving an open question of Gupta et al. [Gupta et al., 2017].
BibTeX  Entry
@InProceedings{bradac_et_al:LIPIcs:2019:11264,
author = {Domagoj Bradac and Sahil Singla and Goran Zuzic},
title = {{(Near) Optimal Adaptivity Gaps for Stochastic MultiValue Probing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {49:149:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11264},
URN = {urn:nbn:de:0030drops112641},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.49},
annote = {Keywords: stochastic programming, adaptivity gaps, stochastic multivalue probing, submodular functions, kextendible systems, adaptive strategy, matroid inter}
}
Keywords: 

stochastic programming, adaptivity gaps, stochastic multivalue probing, submodular functions, kextendible systems, adaptive strategy, matroid inter 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 