mlsanityData to 14 Oct 2026

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

arXiv 2405.14995 ↗First posted 23 May 2024cs.DS cs.AI cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 2 of its 8 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

2 of 8 references.

References · 2

  1. 2022Minimum Cost Adaptive Submodular Covercited by 5
  2. 2021A Tight Bound for Stochastic Submodular Covercited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Cost-Aware Recovery-Pathway Identification and Bayesian Optimization for Autonomous Materials Discoverycited by 1