Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909355734990848 |
|---|---|
| author | Bai, Xingjian Coester, Christian Cosson, Romain |
| author_facet | Bai, Xingjian Coester, Christian Cosson, Romain |
| contents | Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is a central problem in online algorithms and mobile computing that has been studied for several decades, and which now is essentially resolved in its original formulation. In this paper, we demonstrate that what appears to be an innocuous modification of the problem actually leads to a drastic (exponential) reduction of the competitive ratio. Specifically, we present an algorithm that is $O(\log^2 w)$-competitive for traversing unweighted layered graphs of width $w$. Our algorithm chooses the agent's position simply according to the probability distribution over the current layer that maximizes the sum of entropies of the induced distributions in the preceding layers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16176 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization Bai, Xingjian Coester, Christian Cosson, Romain Data Structures and Algorithms Metric Geometry Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is a central problem in online algorithms and mobile computing that has been studied for several decades, and which now is essentially resolved in its original formulation. In this paper, we demonstrate that what appears to be an innocuous modification of the problem actually leads to a drastic (exponential) reduction of the competitive ratio. Specifically, we present an algorithm that is $O(\log^2 w)$-competitive for traversing unweighted layered graphs of width $w$. Our algorithm chooses the agent's position simply according to the probability distribution over the current layer that maximizes the sum of entropies of the induced distributions in the preceding layers. |
| title | Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization |
| topic | Data Structures and Algorithms Metric Geometry |
| url | https://arxiv.org/abs/2404.16176 |