2022/08/17 by Al-Thani, Hessa, Yubing Cui, Cui, Yubing +2 · 2 citations
Computer Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2208.08351
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 P≠ 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.