Lee, Jae-Ha; Park, Chong-Dae; Chwa, Kyung-Yong

Carrying umbrellas: An online relocation game on a graph

J. Graph Algorithms Appl. 5(5), 3-16 (2001)


Summary: 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: