ON ALGORITHM DESIGN FOR METRICAL TASK SYSTEMS

We extend the definition of Metrical Task System, introduced by Borodi n et al. in [4]. In the extended definition, a system is described by the underlying metric space of states M as well as a set of allowable tasks T. Any request to an algorithm must be a member of T. The extens ion makes the model powerful enough to characterize completely many im portant on-line problems. We consider methods of designing competitive algorithms given the description of a system (M, I). In particular, w e show that it is PSPACE-hard to determine the behavior of a c(M, I)-c ompetitive algorithm, where c(M, I) is the best possible competitive r atio on (M, I). In addition, we show a simple, polynomial-rime algorit hm for task systems [U-n, I] (where U-n is the uniform metric space on n nodes) that achieves a competitive ratio of O(log n . C(M, T)).