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 is defined over items and their states. Our goal is to sequentially select a group of items to achieve a ``goal value'' while minimizing the maximum cost across realizations (a.k.a. worst-case cost). To facilitate our study, we introduce a broad class of stochastic functions, called \emph{worst-case submodular function}. Assume the utility function is worst-case submodular, we develop a tight $(\log (Q/\eta)+1)$-approximation policy, where $Q$ is the ``goal value'' and $\eta$ is the minimum gap between $Q$ and any attainable utility value $\hat{Q}<Q$. We also study a worst-case maximum-coverage problem, whose goal is to select a group of items to maximize its worst-case utility subject to a budget constraint. This is a flipped problem of the minimum-cost-cover problem, and to solve this problem, we develop a tight $(1-1/e)$-approximation solution.

本文研究自适应子模块覆盖问题，在最坏情况下进行研究。该问题推广了许多以前研究过的问题，对于固定成本下观察每个医学测试的结果的效用函数，我们目的是选择一组物品以实现“目标值”，并在最小化实现代价（最大较差情况下成本）的同时逐步选择这些物品。同时研究了最坏情况下的最大覆盖问题。

最坏情况下的自适应亚模模糊覆盖