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 $4·(1+\ln \hspace{0.17em}Q)$, where Q is the goal value. We also show that the greedy policy has approximation ratio of at least $1.3·(1+\ln \hspace{0.17em}Q)$ even when $Q=1$, 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 ${(p+1)}^{p+1}·{(\ln \hspace{0.17em}Q+1)}^p$ approximation guarantee for all $p\ge 1$. All our approximation ratios are best possible up to constant factors (assuming $P\ne NP$). 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.