Minimum Cost Adaptive Submodular Cover

• 成果类型: Article; Early Access
• 署名作者: Al-Thani, Hessa; Cui, Yubing; Harris, Blake; Nagarajan, Viswanath
• 署名单位: University of Michigan; University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0548
• 发表日期: 2026-06-04
• 关键词: stochastic optimization; Submodularity; Approximation algorithms

摘要

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 covering an adaptive submodular function at minimum expected cost, where the random realizations of different items may be correlated. We show that the natural greedy policy has an approximation ratio of 4 center dot (1 + ln Q), where Q is the goal value. We also show that the greedy policy has approximation ratio of at least 1:3 center dot (1 + ln Q) even when Q = 1, which invalidates a prior result on adaptive submodular cover. Moreover, we consider a significantly more general objective of minimizing the pth moment of the coverage cost and show that the greedy policy simultaneously achieves a (p + 1)(p+1) center dot (ln Q + 1)(p) approximation guarantee for all p >= 1. All our approximation ratios are best possible up to constant factors (assuming P not equal NP). Our results also extend to the setting where one wants to cover multiple adaptive submodular functions, for which we obtain the same approximation guarantees.