A framework for distributed discrete evacuation strategies
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908965307154432 |
|---|---|
| author | Borowiecki, Piotr Dereniowski, Dariusz Kuszner, Łukasz |
| author_facet | Borowiecki, Piotr Dereniowski, Dariusz Kuszner, Łukasz |
| contents | In this paper, we study discrete evacuation in networks, where agents know the network topology and designated exit nodes but do not know the number and initial positions of other agents. Each agent initially occupies a distinct node and must reach any exit node. Operating in a synchronous distributed model with local communication, the agents aim to minimize the time when the last agent reaches an exit. We introduce a general algorithmic framework for constructing evacuation strategies on arbitrary graphs. As a key application, we demonstrate that the framework yields asymptotically optimal evacuation strategies -- achieving a constant competitive ratio -- for grid networks, with natural extensions to triangular and hexagonal grids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14052 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A framework for distributed discrete evacuation strategies Borowiecki, Piotr Dereniowski, Dariusz Kuszner, Łukasz Discrete Mathematics 68R10, 68W05 G.2.2 In this paper, we study discrete evacuation in networks, where agents know the network topology and designated exit nodes but do not know the number and initial positions of other agents. Each agent initially occupies a distinct node and must reach any exit node. Operating in a synchronous distributed model with local communication, the agents aim to minimize the time when the last agent reaches an exit. We introduce a general algorithmic framework for constructing evacuation strategies on arbitrary graphs. As a key application, we demonstrate that the framework yields asymptotically optimal evacuation strategies -- achieving a constant competitive ratio -- for grid networks, with natural extensions to triangular and hexagonal grids. |
| title | A framework for distributed discrete evacuation strategies |
| topic | Discrete Mathematics 68R10, 68W05 G.2.2 |
| url | https://arxiv.org/abs/2504.14052 |