Adaptivity gaps for stochastic probing: Submodular and XOS functions

Anupam Gupta, Viswanath Nagarajan, Sahil Singla

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

17 Scopus citations

Abstract

Suppose we are given a submodular function f over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for such problems under both monotone and non-monotone submodular functions. We consider these problems in a stochastic setting, where elements are not all active and we only get value from active elements. Each element e is active independently with some known probability pe, but we don't know the element's status a priori: we find it out only when we probe the element e. Moreover, the sequence of elements we probe must satisfy a given prefix-closed constraint, e.g., matroid, orienteering, deadline, precedence, or any downward-closed constraint. In this paper we study the gap between adaptive and non-adaptive strategies for f being a submodular or a fractionally subadditive (XOS) function. If this gap is small, we can focus on finding good non-adaptive strategies instead, which are easier to find as well as to represent. We show that the adaptivity gap is a constant for monotone and non-monotone submodular functions, and logarithmic for XOS functions of small width. These bounds are nearly tight. Our techniques show new ways of arguing about the optimal adaptive decision tree for stochastic optimization problems.

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages1688-1702
Number of pages15
ISBN (Electronic)9781611974782
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

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

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Adaptivity gaps for stochastic probing: Submodular and XOS functions'. Together they form a unique fingerprint.

  • Cite this

    Gupta, A., Nagarajan, V., & Singla, S. (2017). Adaptivity gaps for stochastic probing: Submodular and XOS functions. In P. N. Klein (Ed.), 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1688-1702). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 0). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974782.111