Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
<|reference_start|>Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover: 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.<|reference_end|>
@article{harris2024lower,
    title={Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular
  Cover},
    author={Blake Harris and Viswanath Nagarajan},
    journal={arXiv preprint arXiv:2405.14995},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14995},
    primaryClass={cs.DS cs.AI cs.LG}
}