- Award ID(s):
- 2245674
- PAR ID:
- 10440717
- Date Published:
- Journal Name:
- SIAM Journal on Scientific Computing
- Volume:
- 45
- Issue:
- 1
- ISSN:
- 1064-8275
- Page Range / eLocation ID:
- B57 to B77
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
We provide faster algorithms for approximating the optimal transport distance, e.g. earth mover's distance, between two discrete probability distributions on n elements. We present two algorithms that compute couplings between marginal distributions with an expected transportation cost that is within an additive ϵ of optimal in time O(n^2/eps); one algorithm is straightforward to parallelize and implementable in depth O(1/eps). Further, we show that additional improvements on our results must be coupled with breakthroughs in algorithmic graph theory.more » « less
-
Abstract In the absence of drugs and vaccines, policymakers use non-pharmaceutical interventions such as social distancing to decrease rates of disease-causing contact, with the aim of reducing or delaying the epidemic peak. These measures carry social and economic costs, so societies may be unable to maintain them for more than a short period of time. Intervention policy design often relies on numerical simulations of epidemic models, but comparing policies and assessing their robustness demands clear principles that apply across strategies. Here we derive the theoretically optimal strategy for using a time-limited intervention to reduce the peak prevalence of a novel disease in the classic Susceptible-Infectious-Recovered epidemic model. We show that broad classes of easier-to-implement strategies can perform nearly as well as the theoretically optimal strategy. But neither the optimal strategy nor any of these near-optimal strategies is robust to implementation error: small errors in timing the intervention produce large increases in peak prevalence. Our results reveal fundamental principles of non-pharmaceutical disease control and expose their potential fragility. For robust control, an intervention must be strong, early, and ideally sustained.