The Power of Adaptivity for Stochastic Submodular Cover
Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan
Operations Research · 2024 · Volume 72 · Issue 3
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. Funding: R. Ghuge and V. Nagarajan were supported in part by the National Science Foundation (NSF) Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1940766] and Division of Computing and Communication Foundations [Grant CCF-2006778]. A. Gupta was supported in part by the NSF [Grants CCF-1907820, CCF1955785, and CCF-2006953]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2388 .
Keywords
Optimization, submodularity, stochastic optimization, rounds of adaptivity, covering problems
Enable JavaScript for citation tools and additional paper interactions.