Algorithms and adaptivity gaps for stochastic probing

Anupam Gupta, Viswanath Nagarajan, Sahil Singla

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

10 Scopus citations

Abstract

A stochastic probing problem consists of a set of elements whose values are independent random variables. The algorithm knows the distributions of these variables, but not the actual outcomes. The only way to learn the actual outcomes is to probe these elements. However, there are constraints on which set of elements may be probed. (E.g., we may have to travel in some metric to probe elements but have limited time.) These constraints are called outer constraints. We want to develop an algorithm that picks some set of elements to maximize the (expected) value, subject to the picked subset of elements satisfying some other set of constraints, called the inner constraints. In the past, probing problems were studied for the case when both inner and outer constraints were intersections of matroids; these modeled kidney matching and Bayesian auctions applications. One limitation of past work was their reliance on linear-programming-like techniques, which made going beyond matroid-like structures difficult. In this work, we give a very general adaptivity gap result that holds for all prefix-closed outer constraints, as long as the inner constraints are intersections of matroids. The adaptivity gap is O(logn) for any constant number of inner matroid constraints. The prefix-closedness captures most "reasonable" outer constraints, like orienteering, connectivity, and precedence. Based on this we obtain the first approximation algorithms for a number of stochastic probing problems, which have applications, e.g., to path-planning and precedence-constrained scheduling.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1731-1747
Number of pages17
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume3

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Algorithms and adaptivity gaps for stochastic probing'. Together they form a unique fingerprint.

  • Cite this

    Gupta, A., Nagarajan, V., & Singla, S. (2016). Algorithms and adaptivity gaps for stochastic probing. In R. Krauthgamer (Ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (pp. 1731-1747). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 3). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974331.ch120