The Power of Adaptivity for Stochastic Submodular Cover

• 成果类型: Article
• 署名作者: Ghuge, Rohan; Gupta, Anupam; Nagarajan, Viswanath
• 署名单位: University of Michigan System; University of Michigan; Carnegie Mellon University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2388
• 发表日期: 2024
• 页码: 1156-1176
• 关键词: decision trees; Approximation algorithms; selection; greedy; bounds

摘要

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 are as as solutions.