Abstract: The efficient detection of outbreaks and other cascading phenomena is a fundamental problem in a number of domains, including disease spread, social networks, and infrastructure networks. In such settings, monitoring and testing a small group of pre-selected susceptible population (i.e., sensor set) is often the preferred testing regime---we refer to this as the MinDelSS problem. Prior methods for minimizing the detection time rely on greedy algorithms using submodularity. We show that this approach can lead to sometimes lead to a worse approximation for minimizing the detection time than desired. We also show that \prob{} is hard to approximate within an $O(n^{1-1/\gamma})$-factor for any constant $\gamma\geq 2$ (n is the number of nodes in the graph), which motivates our bicriteria approximations. We present the algorithm \algo{}, which gives a

rigorous worst case $O(\log{n})$-factor for the detection time, while violating the budget by a factor of $O(\log^2{n})$. Our algorithm is based on the sample average approximation technique from stochastic optimization, combined with linear programming and rounding. We evaluate our algorithm on several networks, including hospital contact networks, which validates its effectiveness in real settings.