Home Issues About JGAA Instructions for Authors
 
 
Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
DOI: 10.7155/jgaa.00037
Carrying Umbrellas: an Online Relocation Game on a Graph
Vol. 5, no. 5, pp. 3-16, 2001. Regular paper.
Abstract 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.
Submitted: December 1998.
Revised: March 2000.
Revised: July 2000.
Communicated by Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner
article (PDF)
BibTeX