3.9 Article

The Cost of Uncertainty in Curing Epidemics

出版社

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3219617.3219622

关键词

contagion; contact process on graph; controlled SI model; time to extinction; partial information

资金

  1. National Science Foundation [1704778, 1609279]
  2. Direct For Computer & Info Scie & Enginr
  3. Division Of Computer and Network Systems [1704778] Funding Source: National Science Foundation
  4. Div Of Electrical, Commun & Cyber Sys
  5. Directorate For Engineering [1609279] Funding Source: National Science Foundation

向作者/读者索取更多资源

Motivated by the study of controlling (curing) epidemics, we consider the spread of an SI process on a known graph, where we have a limited budget to use to transition infected nodes back to the susceptible state (i.e., to cure nodes). Recent work has demonstrated that under perfect and instantaneous information (which nodes are/are not infected), the budget required for curing a graph precisely depends on a combinatorial property called the CutWidth. We show that this assumption is in fact necessary: even a minor degradation of perfect information, e.g., a diagnostic test that is 99% accurate, drastically alters the landscape. Infections that could previously be cured in sublinear time now may require exponential time, or orderwise larger budget to cure. The crux of the issue comes down to a tension not present in the full information case: if a node is suspected (but not certain) to be infected, do we risk wasting our budget to try to cure an uninfected node, or increase our certainty by longer observation, at the risk that the infection spreads further? Our results present fundamental, algorithm-independent bounds that tradeoff budget required vs. uncertainty.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

3.9
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据