Worst-Case Adaptive Submodular Cover

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 a 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(𝑄/𝜂) + 1)-approximation policy, where 𝑄 is the “target value” and 𝜂 is the smallest difference between 𝑄 and any achievable utility value ˆ 𝑄 < 𝑄. We also study a worst-case maximum-coverage problem, a dual problem of the minimum-costcover 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/𝑒)/2-approximation solution.

Authors

• Jing Yuan University of North Texas
• Shaojie Tang Department of Management Science and Systems, University at Buffalo, Buffalo, New York, United States

Keywords

• Adaptive submodular maximization
• Worst-case analysis
• Approximation algorithms