The Power of Adaptivity for Stochastic Submodular Cover

Rohan Ghuge (), Anupam Gupta () and Viswanath Nagarajan ()
Additional contact information
Rohan Ghuge: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
Anupam Gupta: Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Viswanath Nagarajan: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2024, vol. 72, issue 3, 1156-1176

Abstract: In the stochastic submodular cover problem, the goal is to select a subset of stochastic items of minimum expected cost to cover a submodular function. Solutions in this setting correspond to sequential decision processes that select items one by one adaptively (depending on prior observations). Whereas such adaptive solutions achieve the best objective, the inherently sequential nature makes them undesirable in many applications. We show how to obtain solutions that approximate fully adaptive solutions using only a few “rounds” of adaptivity. We study both independent and correlated settings, proving smooth trade-offs between the number of adaptive rounds and the solution quality. Experiments on synthetic and real data sets show qualitative improvements in the solutions as we allow more rounds of adaptivity; in practice, solutions with a few rounds of adaptivity are nearly as good as fully adaptive solutions.

Keywords: Optimization; submodularity; stochastic optimization; rounds of adaptivity; covering problems (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2388 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:3:p:1156-1176

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().