Lazy On-Line Algorithms for Metrical Service Systems

Area 09 – Ingegneria industriale e dell'informazione

In this paper we consider the problem of efficiently serving a sequence of requests in an on-line fashion, where every request is a subset of a metric space and serving a request means moving the unique serve to a point of the subset. Problems of this kind are called metrical service systems (MSS) and are a generalization of problems such as paging, the k.serve problem and the so-called CNN problem.In this context, we give a general definition of lazy algorithm for MSS and show that lazy algorithms are as powerful as genale algorithms; in particular, the optimal algorith, is lazy without loss of generality. We also aanalyze two special cases of MSS, related to the CNN problem, and give an upped bound on thei competitive ratio using the lazinezz of OPT.Finally, we present the results of an application of an algorithm described by Chrobak and Larmore to decide the c-competitiveness od an MSS to some MSS on finite spaces, including particular cases od the CNN problem

SINTESI