Eintrag weiter verarbeiten
Complexity among combinatorial problems from epidemics
Gespeichert in:
| Zeitschriftentitel: | International Transactions in Operational Research |
|---|---|
| Personen und Körperschaften: | , , |
| In: | International Transactions in Operational Research, 25, 2018, 1, S. 295-318 |
| Format: | E-Article |
| Sprache: | Englisch |
| veröffentlicht: |
Wiley
|
| Schlagwörter: |
| author_facet |
Piccini, Juan Robledo, Franco Romero, Pablo Piccini, Juan Robledo, Franco Romero, Pablo |
|---|---|
| author |
Piccini, Juan Robledo, Franco Romero, Pablo |
| spellingShingle |
Piccini, Juan Robledo, Franco Romero, Pablo International Transactions in Operational Research Complexity among combinatorial problems from epidemics Management of Technology and Innovation Management Science and Operations Research Strategy and Management Computer Science Applications Business and International Management |
| author_sort |
piccini, juan |
| spelling |
Piccini, Juan Robledo, Franco Romero, Pablo 0969-6016 1475-3995 Wiley Management of Technology and Innovation Management Science and Operations Research Strategy and Management Computer Science Applications Business and International Management http://dx.doi.org/10.1111/itor.12444 <jats:title>Abstract</jats:title><jats:p>A cornerstone in epidemic modeling is the classical susceptible–infected–removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity from further contact with infected individuals). Transitions <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0001.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0001" /> occur at constant rates <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0002.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0002" />. The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph‐theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0003.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0003" />‐complete problems. As a corollary, SIR‐based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path‐relinking post‐optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real‐life applications.</jats:p> Complexity among combinatorial problems from epidemics International Transactions in Operational Research |
| doi_str_mv |
10.1111/itor.12444 |
| facet_avail |
Online |
| finc_class_facet |
Wirtschaftswissenschaften Informatik |
| format |
ElectronicArticle |
| fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMS9pdG9yLjEyNDQ0 |
| id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMS9pdG9yLjEyNDQ0 |
| institution |
DE-Ch1 DE-L229 DE-D275 DE-Bn3 DE-Brt1 DE-D161 DE-Gla1 DE-Zi4 DE-15 DE-Pl11 DE-Rs1 DE-105 DE-14 |
| imprint |
Wiley, 2018 |
| imprint_str_mv |
Wiley, 2018 |
| issn |
0969-6016 1475-3995 |
| issn_str_mv |
0969-6016 1475-3995 |
| language |
English |
| mega_collection |
Wiley (CrossRef) |
| match_str |
piccini2018complexityamongcombinatorialproblemsfromepidemics |
| publishDateSort |
2018 |
| publisher |
Wiley |
| recordtype |
ai |
| record_format |
ai |
| series |
International Transactions in Operational Research |
| source_id |
49 |
| title |
Complexity among combinatorial problems from epidemics |
| title_unstemmed |
Complexity among combinatorial problems from epidemics |
| title_full |
Complexity among combinatorial problems from epidemics |
| title_fullStr |
Complexity among combinatorial problems from epidemics |
| title_full_unstemmed |
Complexity among combinatorial problems from epidemics |
| title_short |
Complexity among combinatorial problems from epidemics |
| title_sort |
complexity among combinatorial problems from epidemics |
| topic |
Management of Technology and Innovation Management Science and Operations Research Strategy and Management Computer Science Applications Business and International Management |
| url |
http://dx.doi.org/10.1111/itor.12444 |
| publishDate |
2018 |
| physical |
295-318 |
| description |
<jats:title>Abstract</jats:title><jats:p>A cornerstone in epidemic modeling is the classical susceptible–infected–removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity from further contact with infected individuals). Transitions <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0001.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0001" /> occur at constant rates <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0002.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0002" />. The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph‐theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0003.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0003" />‐complete problems. As a corollary, SIR‐based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path‐relinking post‐optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real‐life applications.</jats:p> |
| container_issue |
1 |
| container_start_page |
295 |
| container_title |
International Transactions in Operational Research |
| container_volume |
25 |
| format_de105 |
Article, E-Article |
| format_de14 |
Article, E-Article |
| format_de15 |
Article, E-Article |
| format_de520 |
Article, E-Article |
| format_de540 |
Article, E-Article |
| format_dech1 |
Article, E-Article |
| format_ded117 |
Article, E-Article |
| format_degla1 |
E-Article |
| format_del152 |
Buch |
| format_del189 |
Article, E-Article |
| format_dezi4 |
Article |
| format_dezwi2 |
Article, E-Article |
| format_finc |
Article, E-Article |
| format_nrw |
Article, E-Article |
| _version_ |
1792334106353205252 |
| geogr_code |
not assigned |
| last_indexed |
2024-03-01T14:22:57.223Z |
| geogr_code_person |
not assigned |
| openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=Complexity+among+combinatorial+problems+from+epidemics&rft.date=2018-01-01&genre=article&issn=1475-3995&volume=25&issue=1&spage=295&epage=318&pages=295-318&jtitle=International+Transactions+in+Operational+Research&atitle=Complexity+among+combinatorial+problems+from+epidemics&aulast=Romero&aufirst=Pablo&rft_id=info%3Adoi%2F10.1111%2Fitor.12444&rft.language%5B0%5D=eng |
| SOLR | |
| _version_ | 1792334106353205252 |
| author | Piccini, Juan, Robledo, Franco, Romero, Pablo |
| author_facet | Piccini, Juan, Robledo, Franco, Romero, Pablo, Piccini, Juan, Robledo, Franco, Romero, Pablo |
| author_sort | piccini, juan |
| container_issue | 1 |
| container_start_page | 295 |
| container_title | International Transactions in Operational Research |
| container_volume | 25 |
| description | <jats:title>Abstract</jats:title><jats:p>A cornerstone in epidemic modeling is the classical susceptible–infected–removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity from further contact with infected individuals). Transitions <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0001.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0001" /> occur at constant rates <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0002.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0002" />. The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph‐theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0003.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0003" />‐complete problems. As a corollary, SIR‐based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path‐relinking post‐optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real‐life applications.</jats:p> |
| doi_str_mv | 10.1111/itor.12444 |
| facet_avail | Online |
| finc_class_facet | Wirtschaftswissenschaften, Informatik |
| format | ElectronicArticle |
| format_de105 | Article, E-Article |
| format_de14 | Article, E-Article |
| format_de15 | Article, E-Article |
| format_de520 | Article, E-Article |
| format_de540 | Article, E-Article |
| format_dech1 | Article, E-Article |
| format_ded117 | Article, E-Article |
| format_degla1 | E-Article |
| format_del152 | Buch |
| format_del189 | Article, E-Article |
| format_dezi4 | Article |
| format_dezwi2 | Article, E-Article |
| format_finc | Article, E-Article |
| format_nrw | Article, E-Article |
| geogr_code | not assigned |
| geogr_code_person | not assigned |
| id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMS9pdG9yLjEyNDQ0 |
| imprint | Wiley, 2018 |
| imprint_str_mv | Wiley, 2018 |
| institution | DE-Ch1, DE-L229, DE-D275, DE-Bn3, DE-Brt1, DE-D161, DE-Gla1, DE-Zi4, DE-15, DE-Pl11, DE-Rs1, DE-105, DE-14 |
| issn | 0969-6016, 1475-3995 |
| issn_str_mv | 0969-6016, 1475-3995 |
| language | English |
| last_indexed | 2024-03-01T14:22:57.223Z |
| match_str | piccini2018complexityamongcombinatorialproblemsfromepidemics |
| mega_collection | Wiley (CrossRef) |
| physical | 295-318 |
| publishDate | 2018 |
| publishDateSort | 2018 |
| publisher | Wiley |
| record_format | ai |
| recordtype | ai |
| series | International Transactions in Operational Research |
| source_id | 49 |
| spelling | Piccini, Juan Robledo, Franco Romero, Pablo 0969-6016 1475-3995 Wiley Management of Technology and Innovation Management Science and Operations Research Strategy and Management Computer Science Applications Business and International Management http://dx.doi.org/10.1111/itor.12444 <jats:title>Abstract</jats:title><jats:p>A cornerstone in epidemic modeling is the classical susceptible–infected–removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity from further contact with infected individuals). Transitions <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0001.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0001" /> occur at constant rates <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0002.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0002" />. The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph‐theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12444-math-0003.png" xlink:title="urn:x-wiley:09696016:media:itor12444:itor12444-math-0003" />‐complete problems. As a corollary, SIR‐based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path‐relinking post‐optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real‐life applications.</jats:p> Complexity among combinatorial problems from epidemics International Transactions in Operational Research |
| spellingShingle | Piccini, Juan, Robledo, Franco, Romero, Pablo, International Transactions in Operational Research, Complexity among combinatorial problems from epidemics, Management of Technology and Innovation, Management Science and Operations Research, Strategy and Management, Computer Science Applications, Business and International Management |
| title | Complexity among combinatorial problems from epidemics |
| title_full | Complexity among combinatorial problems from epidemics |
| title_fullStr | Complexity among combinatorial problems from epidemics |
| title_full_unstemmed | Complexity among combinatorial problems from epidemics |
| title_short | Complexity among combinatorial problems from epidemics |
| title_sort | complexity among combinatorial problems from epidemics |
| title_unstemmed | Complexity among combinatorial problems from epidemics |
| topic | Management of Technology and Innovation, Management Science and Operations Research, Strategy and Management, Computer Science Applications, Business and International Management |
| url | http://dx.doi.org/10.1111/itor.12444 |