Carrying Umbrellas: an Online Relocation Game on a Graph
| Autor: | Chong-Dae Park, Kyung Yong Chwa, Jae-Ha Lee |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Theoretical computer science
Computational Theory and Mathematics General Computer Science Competitive analysis Computer science Distributed computing Competitive algorithm Graph (abstract data type) Geometry and Topology Online algorithm Relocation Computer Science Applications Theoretical Computer Science |
| Zdroj: | Journal of Graph Algorithms and Applications. 5:3-16 |
| ISSN: | 1526-1719 |
| DOI: | 10.7155/jgaa.00037 |
| Popis: | We introduce an online relocation problem on a graph, in which a player that walks around the vertices makes decisions on whether to relocate mobile resources, while not knowing the future requests. We call it Carrying Umbrellas. This paper gives a necessary and sucient condition under which a competitive algorithm exists. We also describe an online algorithm and analyze its competitive ratio. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|