Carrying Umbrellas: An Online Relocation Problem on Graphs?

Abstract. We introduce an online relocation problem on a graph, in which a player who walks around the nodes 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 and describes an optimal algorithm and anaylzes its competitve ratio. We also extend this problem to the case of digraphs.