Minimum Cost Adaptive Submodular Cover
Yubing Cui, Viswanath Nagarajan · Society for Industrial and Applied Mathematics eBooks · 2023
We consider the problem of minimum cost cover of adaptive-submodular functions, and provide a 4(ln Q+1)- approximation algorithm, where Q is the goal value. This bound is nearly the best possible as the problem does not admit any approximation ratio better than ln Q (unless P = NP). Our result is the first O(ln Q)-approximation algorithm for this problem. Previously, O(ln Q)-approximation algorithms were only known assuming either independent items or unit-cost items. Furthermore, our result easily extends to the setting where one wants to simultaneously cover multiple adaptive-submodular functions: we obtain the first approximation algorithm for this generalization.