2 papers
cs.DS2025
Sequential Testing with Subadditive Costs
Blake Harris, Viswanath Nagarajan, Rayen Tan
In the classic sequential testing problem, we are given a system with several components each of which fails with some independent probability. The goal is to identify whether or n…
cs.DS2024
Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
Blake Harris, Viswanath Nagarajan
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 invalid…