On efficient vaccine distribution strategy to suppress pandemic using social relation
| Autor: | Sung-Sik Kwon, Donghyun Kim, Alade O. Tokuta, Hao Guo, Wei Wang, Joong-Lyul Lee |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Graph theory 0102 computer and information sciences 02 engineering and technology Directed acyclic graph 01 natural sciences Graph bandwidth 010201 computation theory & mathematics Cut 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Graph (abstract data type) 020201 artificial intelligence & image processing Closure problem Time complexity Mathematics Moral graph |
| Zdroj: | Discrete Mathematics, Algorithms and Applications. :1650010 |
| ISSN: | 1793-8317 1793-8309 |
| DOI: | 10.1142/s1793830916500105 |
| Popis: | In this paper, we investigate the problem of how to distribute vaccines, which will be supplied over time, so that the number of the infected can be minimized during a given mission period. The concept of temporal graph is adopted to abstract the constantly changing social relations over time. Then, we formally introduce the social-relation-based vaccine distribution planning problem (SVDP2) on the temporal graph. To solve the problem, we first introduce a new graph induction technique to combine the subgraphs in the temporal graph into a single directed acyclic graph. Then, we design a new technique based on a maximum flow algorithm to evaluate the quality of any feasible solution of the problem. Finally, we propose an enumeration algorithm which will search the solution space using the evaluation technique and find the best possible solution within polynomial time. Our simulation result shows the proposed algorithm is more efficient than a simple strategy which randomly distributes vaccines. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|