A lower bound on the performance of dynamic curing policies for epidemics on graphs
We consider an SIS-type epidemic process that evolves on a known graph. We assume that a fixed curing budget can be allocated at each instant to the nodes of the graph, towards the objective of minimizing the expected extinction time of the epidemic. We provide a lower bound on the optimal expected...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111682 https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1811093495397482496 |
|---|---|
| author | Drakopoulos, Kimon Koksal, Asuman E. Tsitsiklis, John N |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Drakopoulos, Kimon Koksal, Asuman E. Tsitsiklis, John N |
| author_sort | Drakopoulos, Kimon |
| collection | MIT |
| description | We consider an SIS-type epidemic process that evolves on a known graph. We assume that a fixed curing budget can be allocated at each instant to the nodes of the graph, towards the objective of minimizing the expected extinction time of the epidemic. We provide a lower bound on the optimal expected extinction time as a function of the available budget, the epidemic parameters, the maximum degree, and the CutWidth of the graph. For graphs with large CutWidth (close to the largest possible), and under a budget which is sublinear in the number of nodes, our lower bound scales exponentially with the size of the graph. |
| first_indexed | 2024-09-23T15:45:46Z |
| format | Article |
| id | mit-1721.1/111682 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:45:46Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1116822022-09-29T16:00:53Z A lower bound on the performance of dynamic curing policies for epidemics on graphs Drakopoulos, Kimon Koksal, Asuman E. Tsitsiklis, John N Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Drakopoulos, Kimon Koksal, Asuman E. Tsitsiklis, John N We consider an SIS-type epidemic process that evolves on a known graph. We assume that a fixed curing budget can be allocated at each instant to the nodes of the graph, towards the objective of minimizing the expected extinction time of the epidemic. We provide a lower bound on the optimal expected extinction time as a function of the available budget, the epidemic parameters, the maximum degree, and the CutWidth of the graph. For graphs with large CutWidth (close to the largest possible), and under a budget which is sublinear in the number of nodes, our lower bound scales exponentially with the size of the graph. United States. Army Research Office (Grant W911NF-12-1-0509) National Science Foundation (U.S.) (Grant CMMI-1234062) 2017-10-03T18:26:11Z 2017-10-03T18:26:11Z 2016-02 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-7886-1 http://hdl.handle.net/1721.1/111682 Drakopoulos, Kimon et al. “A Lower Bound on the Performance of Dynamic Curing Policies for Epidemics on Graphs.” 2015 54th IEEE Conference on Decision and Control (CDC), December 15-18 2015, Osaka, Japan, Institute of Electrical and Electronics Engineers (IEEE), February 2016: 3560-3567 © 2015 Institute of Electrical and Electronics Engineers (IEEE) https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/CDC.2015.7402770 2015 54th IEEE Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Drakopoulos, Kimon Koksal, Asuman E. Tsitsiklis, John N A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title | A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title_full | A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title_fullStr | A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title_full_unstemmed | A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title_short | A lower bound on the performance of dynamic curing policies for epidemics on graphs |
| title_sort | lower bound on the performance of dynamic curing policies for epidemics on graphs |
| url | http://hdl.handle.net/1721.1/111682 https://orcid.org/0000-0001-8288-5874 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT drakopouloskimon alowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs AT koksalasumane alowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs AT tsitsiklisjohnn alowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs AT drakopouloskimon lowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs AT koksalasumane lowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs AT tsitsiklisjohnn lowerboundontheperformanceofdynamiccuringpoliciesforepidemicsongraphs |