On-Line Algorithms for Robot Navigation and Server Problems

Abstract

Many classical problems of computer science --- such as paging, scheduling, and maintaining dynamic data structures --- are naturally on-line; an algorithm for such a problem is constantly making irrevocable decisions without knowing what its future input will be. The competitive analysis of on-line algorithms was broughtinto prominence by the work of Sleator and Tarjan in 1985 as a theoretical framework in which to measure the performance of such algorithms. Since then, a variety of on-line problems have been studied from this perspective. We consider