Showing cs.DSShow all
3 papers · 1 filter
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…
cs.DS2023
Informative Path Planning with Limited Adaptivity
Rayen Tan, Rohan Ghuge, Viswanath Nagarajan
We consider the informative path planning () problem in which a robot interacts with an uncertain environment and gathers information by visiting locations. The goal…