# Minimum Cost Adaptive Submodular Cover

arXiv: https://arxiv.org/abs/2208.08351 · HTML: https://mlsanity.com/paper/2208.08351/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 31 references that are in the map.
- First posted on arXiv 17 Aug 2022.

## Builds on (most cited first, 9 of 9)

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions](https://mlsanity.com/paper/1608.00673/) (2016)
- [Submodular Stochastic Probing on Matroids](https://mlsanity.com/paper/1310.4415/) (2013)
- [Adaptive Influence Maximization in Dynamic Social Networks](https://mlsanity.com/paper/1506.06294/) (2015)
- [Stochastic Submodular Cover with Limited Adaptivity](https://mlsanity.com/paper/1810.13351/) (2018)
- [(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing](https://mlsanity.com/paper/1902.01461/) (2019)
- [A Tight Bound for Stochastic Submodular Cover](https://mlsanity.com/paper/2102.01149/) (2021)
- [The Power of Adaptivity for Stochastic Submodular Cover](https://mlsanity.com/paper/2106.16115/) (2021)
- [Scenario Submodular Cover](https://mlsanity.com/paper/1603.03158/) (2016)

## Built on by (most cited first, 5 of 5)

- [A Simple Approximation Algorithm for Optimal Decision Tree](https://mlsanity.com/paper/2505.15641/) (2025)
- [Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover](https://mlsanity.com/paper/2405.14995/) (2024)
- [Precedence-Constrained Decision Trees and Coverings](https://mlsanity.com/paper/2602.21312/) (2026)
- [Cost-Aware Recovery-Pathway Identification and Bayesian Optimization for Autonomous Materials Discovery](https://mlsanity.com/paper/2607.23896/) (2026)
- [Worst-Case Adaptive Submodular Cover](https://mlsanity.com/paper/2210.13694/) (2022)

## Abstract (arXiv)

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 adaptive-submodular 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 pth moment of the coverage cost, and show that our algorithm simultaneously achieves a (p+1)p+1· (ln Q+1)p approximation guarantee for all p≥ 1. All our approximation ratios are best possible up to constant factors (assuming Pne NP). Moreover, our results also extend to the setting where one wants to cover em multiple adaptive-submodular functions. Finally, we evaluate the empirical performance of our algorithm on instances of hypothesis identification.