The Power of Adaptivity for Stochastic Submodular Cover

Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1156-1176
Number of pages21
JournalOperations Research
Issue number3
StatePublished - May 1 2024


  • covering problems
  • rounds of adaptivity
  • stochastic optimization
  • submodularity

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'The Power of Adaptivity for Stochastic Submodular Cover'. Together they form a unique fingerprint.

Cite this