Minimum Cost Adaptive Submodular Cover

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.