# Worst-Case Adaptive Submodular Cover

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 25 Oct 2022.

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

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and k-System Constraints](https://mlsanity.com/paper/2104.04853/) (2021)
- [Group Equality in Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.03364/) (2022)
- [Minimum Cost Adaptive Submodular Cover](https://mlsanity.com/paper/2208.08351/) (2022)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Optimizing Ad Allocation in Social Advertising](https://mlsanity.com/paper/1505.03235/) (2015)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Decision Trees for Function Evaluation - Simultaneous Optimization of Worst and Expected Cost](https://mlsanity.com/paper/1309.2796/) (2013)

## Abstract (arXiv)

In this paper, we study the adaptive submodular cover problem under the worst-case setting. This problem generalizes many previously studied problems, namely, the pool-based active learning and the stochastic submodular set cover. The input of our problem is a set of items (e.g., medical tests) and each item has a random state (e.g., the outcome of a medical test), whose realization is initially unknown. One must select an item at a fixed cost in order to observe its realization. There is an utility function which maps a subset of items and their states to a non-negative real number. We aim to sequentially select a group of items to achieve a ``target value'' while minimizing the maximum cost across realizations (a.k.a. worst-case cost). To facilitate our study, we assume that the utility function is worst-case submodular, a property that is commonly found in many machine learning applications. With this assumption, we develop a tight (log (Q/η)+1)-approximation policy, where Q is the ``target value'' and η is the smallest difference between Q and any achievable utility value hatQ<Q. We also study a worst-case maximum-coverage problem, a dual problem of the minimum-cost-cover problem, whose goal is to select a group of items to maximize its worst-case utility subject to a budget constraint. To solve this problem, we develop a (1-1/e)/2-approximation solution.