Carrying Umbrellas: an Online Relocation Game on a Graph
Jae-Ha Lee, Chong-Dae Park, Kyung‐Yong Chwa · Journal of Graph Algorithms and Applications · 2001
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 sufficient condition under which a competitive algorithm exists. We also describe an online algorithm and analyze its competitive ratio. Communicated by T. Nishizeki, R. Tamassia and D. Wagner: