50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Trackless Online Algorithms

Wolfgang Bein University of Nevada, Las Vegas Department of Computer Science

Various models of computation involve restrictions on the power of an algorithm. ``On-line" itself, in fact, is such a restriction. "Bounded memory" is a further restriction which is frequently considered.

A novel concept ``tracklessness" is introduced for the server problem. Tracklessness is a property of an online algorithm which is a restriction on what input data the algorithm uses in its computation, and on what outputs the algorithm gives. Specifically, for each request point, the algorithm is only given as input the distances of the current server positions to the request point. A trackless algorithm may memorize such distance values, but is restricted from storing explicitly any points of the metric space. In the algorithm's response to a request, the algorithm is limited to producing output that identifies which server moves, and does not mention points in the metric space explicitly. Many known algorithms are trackless (e.g. BALANCE, BALANCE_SLACK, RANDOM_SLACK, and HARMONIC) whereas the Workfuntion Algorithm is not trackless. The -server conjecture fails for trackless algorithms. A lower bound of on the competitiveness of any deterministic trackless -server algorithm and a lower bound of on the competitiveness of any randomized trackless -server problem are given.

We then discuss the concept of tracklessness as it applies to paging. Reducing the paging problem to the server problem in a uniform space, the tracklessness restriction translates into the rule that no bookmarks are used. An efficient randomized online algorithm for the paging problem for cache size 2 is given, which is -competitive against an oblivious adversary. The algorithm is almost trackless as it keeps track of at most one page in slow memory at any time. A lower bound of is given for the competitiveness of any trackless online algorithm for the same problem, i.e., an algorithm that keeps track of no page outside the cache.