Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification, and viral marketing. We consider the problem of covering an adaptive submodular function at minimum expected cost, where the random realizations of different items may be correlated. We show that the natural greedy policy has an approximation ratio of Formula: see text, where Q is the goal value. We also show that the greedy policy has approximation ratio of at least Formula: see text even when Formula: see text, which invalidates a prior result on adaptive submodular cover. Moreover, we consider a significantly more general objective of minimizing the pth moment of the coverage cost and show that the greedy policy simultaneously achieves a Formula: see text approximation guarantee for all Formula: see text. All our approximation ratios are best possible up to constant factors (assuming Formula: see text). Our results also extend to the setting where one wants to cover multiple adaptive submodular functions, for which we obtain the same approximation guarantees. Funding: Financial support from the National Science Foundation Division of Computing and Communication Foundations Grant 2418495 and the Qatar National Research Fund QRDI Grant GSRA7-0419-20020 is gratefully acknowledged.
Al-Thani et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: