(Near) optimal adaptivity gaps for stochastic multi-value probing

Domagoj Bradac, Sahil Singla, Goran Zuzic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Consider a kidney-exchange application where we want to find a max-matching 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 pe. 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 non-adaptive strategy always has a value close to the best adaptive strategy. This allows us to focus on designing non-adaptive 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 multi-value 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 (worst-case) adaptivity gaps for multi-value stochastic probing over prefix-closed 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 k-extendible 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. [23].

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019
EditorsDimitris Achlioptas, Laszlo A. Vegh
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771252
DOIs
StatePublished - Sep 2019
Event22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019 - Cambridge, United States
Duration: Sep 20 2019Sep 22 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume145
ISSN (Print)1868-8969

Conference

Conference22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019
CountryUnited States
CityCambridge
Period9/20/199/22/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Adaptive strategy
  • Adaptivity gaps
  • K-extendible systems
  • Matroid intersection
  • Stochastic multi-value probing
  • Stochastic programming
  • Submodular functions

Fingerprint Dive into the research topics of '(Near) optimal adaptivity gaps for stochastic multi-value probing'. Together they form a unique fingerprint.

Cite this