Minimum Cost Adaptive Submodular Cover
Abstract
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 minimum cost cover of adaptivesubmodular functions, and provide a $4(1+\ln Q)$approximation algorithm, where $Q$ is the goal value. In fact, we consider a significantly more general objective of minimizing the $p^{th}$ moment of the coverage cost, and show that our algorithm simultaneously achieves a $(p+1)^{p+1}\cdot (\ln 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$). Moreover, our results also extend to the setting where one wants to cover {\em multiple} adaptivesubmodular functions. Finally, we evaluate the empirical performance of our algorithm on instances of hypothesis identification.
 Publication:

arXiv eprints
 Pub Date:
 August 2022
 DOI:
 10.48550/arXiv.2208.08351
 arXiv:
 arXiv:2208.08351
 Bibcode:
 2022arXiv220808351A
 Keywords:

 Computer Science  Data Structures and Algorithms;
 Computer Science  Machine Learning
 EPrint:
 24 pages, 3 figures