COVID on trees and infinite grids
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914954606542848 |
|---|---|
| author | Barnett, Andrea Bond, Robert Macias, Anthony Mattman, Thomas W. Parnell, Bill Schoenfield, Ely |
| author_facet | Barnett, Andrea Bond, Robert Macias, Anthony Mattman, Thomas W. Parnell, Bill Schoenfield, Ely |
| contents | We use Hartnell's model for virus spread on a graph, also known as firefighting. For rooted trees, we propose an Unburning Algorithm, a type of greedy algorithm starting from the leaves and working back towards the root. We show that the algorithm saves at least half the vertices of the optimal solution and that this is bound is sharp. We confirm a conjecture of Hartke about integrality gaps when comparing linear and integer program solutions. For general graphs, we propose a Containment Protocol, which looks ahead two time steps to decide where to place vaccinations. We show that the protocol performs near optimally on four well-studied infinite grids. The protocol is available for any graph and we realize this flexibility by investigating an infinite pentagonal graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14303 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | COVID on trees and infinite grids Barnett, Andrea Bond, Robert Macias, Anthony Mattman, Thomas W. Parnell, Bill Schoenfield, Ely Combinatorics 05C57, 05C85 (Primary) 92D30 (Secondary) We use Hartnell's model for virus spread on a graph, also known as firefighting. For rooted trees, we propose an Unburning Algorithm, a type of greedy algorithm starting from the leaves and working back towards the root. We show that the algorithm saves at least half the vertices of the optimal solution and that this is bound is sharp. We confirm a conjecture of Hartke about integrality gaps when comparing linear and integer program solutions. For general graphs, we propose a Containment Protocol, which looks ahead two time steps to decide where to place vaccinations. We show that the protocol performs near optimally on four well-studied infinite grids. The protocol is available for any graph and we realize this flexibility by investigating an infinite pentagonal graph. |
| title | COVID on trees and infinite grids |
| topic | Combinatorics 05C57, 05C85 (Primary) 92D30 (Secondary) |
| url | https://arxiv.org/abs/2409.14303 |