Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

Abstract

We show that the greedy algorithm for adaptive-submodular cover has approximation ratio at least 1.3*(1+ln Q). Moreover, the instance demonstrating this gap has Q=1. So, it invalidates a prior result in the paper ``Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization'' by Golovin-Krause, that claimed a (1+ln Q)^2 approximation ratio for the same algorithm.

7 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:2208.08351